planes2.cpp

#include <iostream>
#include <stdio.h>
#include <vector>
#include <functional>
#include <unordered_set>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <queue>
#include <stack>
#include <bitset>

using namespace std;

long long gcd(long long a, long long b)
{
	if (a < 0)
		a = -a;
	if (b < 0)
		b = -b;
	while (a && b)
	{
		if (a > b)
			a %= b;
		else
			b %= a;
	}
	return a ? a : b;
}

const int MOD = 998244353;

long long mult(long long a, long long b) {
	return (a * b) % MOD;
}

void Mult(long long& a, long long b) {
	a *= b;
	a %= MOD;
}

int add(int a, int b) {
	a += b;
	if (a >= MOD)
		return a - MOD;
	return a;
}

int sub(int a, int b) {
	a -= b;
	if (a < 0)
		return a + MOD;
	return a;
}

long long binpow(long long a, long long b) {
	long long res = 1;
	while (b) {
		if (b & 1) {
			Mult(res, a);
		}
		Mult(a, a);
		b >>= 1;
	}
	return res;
}

inline long long inverse(long long x) {
	return binpow(x, MOD - 2);
}

struct fraction
{
	long long a;
	fraction()
	{
		a = 0;
	}
	fraction(long long _a) {
		if (_a < 0)
			_a += MOD;
		a = _a;
	}
	fraction(long long _a, long long _b)
	{
		if (_a < 0)
			_a += MOD;
		a = mult(_a, inverse(_b));
	}
	void relax()
	{
	}
};

fraction operator +(const fraction a, const fraction b)
{
	fraction c(add(a.a, b.a));
	c.relax();
	return c;
}

fraction operator -(const fraction a, const fraction b)
{
	fraction c(sub(a.a, b.a));
	c.relax();
	return c;
}

fraction operator *(const fraction a, const fraction b)
{
	fraction c(mult(a.a, b.a));
	c.relax();
	return c;
}

struct polynomial
{
	vector <fraction> a;
	polynomial()
	{
		a = vector <fraction>(0);
	}
	polynomial(vector<fraction> &c)
	{
		a = c;
	}
	fraction eval(fraction x)
	{
		fraction temp(1, 1);
		fraction ans;
		for (int i = 0; i < a.size(); ++i, temp = temp * x)
			ans = ans + temp * a[i];
		return ans;
	}
};

vector <int> antiderivative(const vector <int> &a)
{
	vector <int> b;
	b.push_back(0);	
	for (int i = 0; i < a.size(); ++i)
		b.push_back(mult(a[i], inverse(i + 1)));
	return b;
}

vector <int> derivative(const vector <int> &a)
{
	vector <int> b;
	for (int i = 1; i < a.size(); ++i)
		b.push_back(mult(a[i], i));
	return b;
}

int generator(int p = MOD) {
	vector<int> fact;
	int phi = p - 1, n = phi;
	for (int i = 2; i*i <= n; ++i)
		if (n % i == 0) {
			fact.push_back(i);
			while (n % i == 0)
				n /= i;
		}
	if (n > 1)
		fact.push_back(n);

	for (int res = 2; res <= p; ++res) {
		bool ok = true;
		for (size_t i = 0; i < fact.size() && ok; ++i)
			ok &= binpow(res, phi / fact[i]) != 1;
		if (ok)  return res;
	}
	return -1;
}

const int G_ROOT = generator();

void fft(vector<int> & a, bool invert) {
	int n = (int)a.size();
	int DEG = (MOD - 1) / n;
	const int root = binpow(G_ROOT, DEG);
	const int root_1 = inverse(root);
	const int root_pw = n;

	for (int i = 1, j = 0; i < n; ++i) {
		int bit = n >> 1;
		for (; j >= bit; bit >>= 1)
			j -= bit;
		j += bit;
		if (i < j)
			swap(a[i], a[j]);
	}

	for (int len = 2; len <= n; len <<= 1) {
		int wlen = invert ? root_1 : root;
		for (int i = len; i < root_pw; i <<= 1)
			wlen = int(wlen * 1ll * wlen % MOD);
		for (int i = 0; i < n; i += len) {
			int w = 1;
			for (int j = 0; j < len / 2; ++j) {
				int u = a[i + j]; 
				int v = mult(a[i + j + len / 2], w);
				a[i + j] = add(u, v);
				a[i + j + len / 2] = sub(u, v);
				w = mult(w, wlen);
			}
		}
	}
	if (invert) {
		int nrev = inverse(n);
		for (int i = 0; i < n; ++i)
			a[i] = mult(a[i], nrev);
	}
}

vector <int> product(vector <int> a, vector <int> b) {
	int n = 1;
	while (n <= (a.size() + b.size())) {
		n <<= 1;
	}
	a.resize(n);
	b.resize(n);
	vector <int> c(n);
	fft(a, false);
	fft(b, false);
	for (int i = 0; i < n; ++i) {
		c[i] = mult(a[i], b[i]);
	}
	fft(c, true);
	while (c.back() == 0) {
		c.pop_back();
	}
	return c;
}

int eval(const vector <int>& a, int x)
{
	int temp = 1;
	int ans = 0;
	for (int i = 0; i < a.size(); ++i, temp = mult(temp, x))
		ans = add(ans, mult(temp, a[i]));
	return ans;
}

int solver(int n, vector <int> t)
{
	sort(t.begin(), t.end());
	vector <int> v = { 1 };
	vector <vector <int>> prod;
	for (int j = 0; j < n; ++j) //only these things can happen on this interval, interval is [t[i - 1]..t[i])
	{
		prod.push_back({ 1, sub(0, inverse(t[j])) });
	}
	std::function<vector<int>(int, int)> multiply, multiply2;
	multiply = [&](int l, int r) {
		if (l == r - 1) {
			return prod[l];
		}
		int mid = (l + r) / 2;
		return product(multiply(l, mid), multiply(mid, r));
	};
	multiply2 = [&](int l, int r) {
		vector <int> vv = { 1 };
		for (int i = l; i < r; ++i) {
			vv = product(vv, prod[i]);
		}
		return vv;
	};
	v = multiply(0, n);
	//auto vv2 = multiply2(0, n);
	//assert(v == multiply2(0, n));
	for (auto& x : v) {
		x = sub(0, x);
	}
	v[0] = add(v[0], 1);
	v = derivative(v);
	vector <int> here;
	here = { 0 };
	for (auto x : v) {
		here.push_back(x);
	}
	v = here;
	v = antiderivative(v);
	int answer = eval(v, t[0]);
	return answer;
}

const int iterations = 1e7;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector <int> t(n);
	for (int i = 0; i < n; ++i)
		cin >> t[i];
	int ans = solver(n, t);
	cout << ans << endl;
	return 0;
}