Given a regular $n$-gon, in addition to its $n$ vertices, there are $a_i - 1$ extra vertices equally spaced along the $i$-th edge in clockwise order. This means the $i$-th edge is divided into $a_i$ segments of equal length by these vertices.

You can connect some line segments between these vertices. After adding the segments, any two newly added segments must only intersect at their endpoints, and no new segment should overlap with the edges of the polygon.

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

Given such a convex polygon, how many ways are there to perform a triangulation that satisfies the above conditions? You only need to calculate the number of ways modulo $998\,244\,353$.

Input

The first line contains an integer $n$, representing the number of edges 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

Output a single integer representing the number of ways to perform the triangulation satisfying the requirements, modulo $998\,244\,353$.

Examples

Input 1

3
2 2 1

Output 1

5

Note 1

There are $5$ ways, as shown in the figure below.

Input 2

5
3 1 4 2 5

Output 2

359895

Input 3

8
4 2 1 8 3 7 3 1

Output 3

577596154

Subtasks

For $10\%$ of the data, $\sum a_i \leq 300$.

For $50\%$ of the data, $\sum a_i \leq 5\,000$.

For $100\%$ of the data, $n \geq 3$, $a_i \geq 1$, and $\sum a_i \leq 5 \times 10^5$.