Problem Description

Given a regular $n$-sided polygon, in addition to the $n$ vertices of this regular $n$-sided polygon, there are $a_i-1$ additional vertices on the $i$-th edge in a clockwise direction, which equally divide this segment. That is, the $i$-th edge is divided into $a_i$ equal segments by these vertices.

You can connect some segments between vertices. However, after connecting the segments, any two newly added segments in the graph can only intersect at their endpoints, and new segments should not overlap with the edges of the polygon.

We call the graph obtained after adding several segments a triangulation if and only if every face inside the polygon is a triangle. Note that the edges of the triangles can have vertices from the original convex polygon.

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

Input Format

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

The second line contains $n$ positive integers, where the $i$-th positive integer is $a_i$, as described in the problem statement.

Output Format

Output a single integer, which is the number of triangulations that meet the requirements modulo $998244353$.

Sample Input and Output

Sample Input #1

3
2 2 1

Sample Output #1

5

Sample Input #2

5
3 1 4 2 5

Sample Output #2

359895

Sample Input #3

8
4 2 1 8 3 7 3 1

Sample Output #3

577596154

Notes

[Sample 1 Explanation]

There are 5 possible triangulations as shown in the figure.

[Data Range]

For $10\%$ of the data, it is guaranteed that $\sum a_{i} \leq 300$.
For $50\%$ of the data, it is guaranteed that $\sum a_{i} \leq 5000$.
For $100\%$ of the data, it is guaranteed that $n \geq 3$, $a_{i} \geq 1$, and $\sum a_{i} \leq 5 \times 10^{5}$.

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

见题面 Input 部分

见题面 Output 部分