Don't Exceed
Contest: Hello 2018
Difficulty rating: 3400
Tags: math, probabilities

You generate real numbers s1, s2, ..., sn as follows:

- s0 = 0;
- si = si - 1 + ti, where ti is a real number chosen independently uniformly at random between 0 and 1, inclusive.

You are given real numbers x1, x2, ..., xn. You are interested in the probability that si ≤ xi is true for all i simultaneously.

It can be shown that this can be represented as $$\frac{p}{q}$$, where P and Q are coprime integers, and $$Q \not\equiv 0 \pmod{998244353}$$. Print the value of P·Q - 1 modulo 998244353.

Input format:
The first line contains integer n (1 ≤ n ≤ 30).

The next n lines contain real numbers x1, x2, ..., xn, given with at most six digits after the decimal point (0 < xi ≤ n).

Output format:
Print a single integer, the answer to the problem.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example, the sought probability is 1 since the sum of i real numbers which don't exceed 1 doesn't exceed i.

In the second example, the probability is x1 itself.

In the third example, the sought probability is 3 / 8.

Example input:
4
1.00
2
3.000000
4.0

Example output:
1

Example input:
1
0.50216

Example output:
342677322

Editorial:
If ti were random integers and not reals, it would be natural to solve the problem using dynamic programming: f(i, j) — the probability that the required inequalities are satisfied if si = j. But in case of real numbers, the probability that a random real number equals to something is zero.
What to do then? A natural solution is to maintain f(i, x) as a function of x, that is, f(i, x) will be the probability density function of si.
What is the form of f(i, x) of x for fixed i? It turns out that this function is piecewise polynomial. Indeed, for i = 1 we have f(i, x) = 1 for x < min(1, x1) and f(i, x) = 0 otherwise. For all i > 1 for x > xi we have f(i, x) = 0, while for x ≤ xi the following identity is true:
For fixed x, what is the value of this integral? Several pieces of f(i - 1, x) fall inside the integration range. The integral of pieces which fall inside entirely is a constant. The integral of the single piece which is close to x (so the start of this piece falls inside the range, but the end of this piece doesn't) is the integral of the corresponding piece of f(i - 1, x), which is an integral of a polynomial, which is a polynomial. Similarly, the integral of the opposite piece (close to x - 1) is the integral of the corresponding piece of f(i - 1, x) under substitution of x - 1, which is also a polynomial. By induction we can see that f(i, x) is a piecewise polynomial function of x.
The solution of the problem is indeed maintaining f(i, x) as polynomials on the corresponding intervals. It's easy to see that polynomials in f(i, x) have degree at most i - 1 (by induction).
To estimate the complexity of this solution, note that the ends of the pieces have the following form: xi + c, where c is an integer. Since we're only interested in the ends of the pieces which are between 0 and n, we have O(n2) pieces overall. Since we have to calculate n layers of DP, each function is a polynomial of degree at most n, and substituting x - 1 into a polynomial takes O(n2), the overall complexity of the solution is O(n5).
Bonus: can you solve the problem in O(n4)?