Problem Description

Given a regular $n$-gon, in addition to its $n$ vertices, on the $i$-th edge in clockwise order there are also extra $a_i - 1$ vertices that divide this segment into equal parts. That is, the $i$-th edge is divided by vertices into $a_i$ segments of equal length.

You may connect some line segments between vertices. After adding these segments, any two newly added segments may intersect only at endpoints. Also, no new segment should overlap with any edge of the polygon.

We call the resulting graph after adding some segments a triangulation if and only if every face inside the polygon is a triangle. Note that the sides of a triangle may contain vertices that lie on the original edges of the convex polygon.

Given such a convex polygon, how many triangulations satisfy the conditions above? You only need to output the number of valid triangulations modulo $998244353$.

Input Format

The first line contains a positive integer $n$, denoting the number of sides of the convex polygon.

The second line contains $n$ positive integers. The $i$-th integer is $a_i$, with the meaning described above.

Output Format

Output one integer in one line, the number of valid triangulations modulo $998244353$.

3
2 2 1

5

5
3 1 4 2 5

359895

8
4 2 1 8 3 7 3 1

577596154

Hint

[Sample 1 Explanation]

There are $5$ valid solutions, as shown in the figure.

[Constraints]

For $10\%$ of the testdata, $\sum a_{i} \leq 300$.
For $50\%$ of the testdata, $\sum a_{i} \leq 5000$.
For $100\%$ of the testdata, $n \geq 3$, $a_{i} \geq 1$, $\sum a_{i} \leq 5 \times 10^{5}$.

Note: There is no large sample download for this problem.

Translated by ChatGPT 5