Problem Description

We will divide $ N $ people into teams such that each person belongs to exactly one team.

However, some people do not want to be in a team with many members.

This condition is represented by an integer sequence $ a $ with $ N $ elements, where the $ i $ -th person must be assigned to a team with at most $ a_{i} $ members.

We want to calculate how many ways we can divide the teams under these conditions. Since the answer can be very large, output the answer modulo $ 998244353 $. Two team divisions are considered different if there exist two people who are in the same team in one division but in different teams in the other division.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ ... $ a_{N-1} $ $ a_N $

Output Format

Output the number of ways to divide the teams under the given conditions modulo $ 998244353 $.

Sample Input and Output

Sample Input #1

1
1

Sample Output #1

1

Sample Input #2

3
3 3 2

Sample Output #2

4

Sample Input #3

10
3 1 4 1 5 9 2 6 3 10

Sample Output #3

1869

Notes/Hints

Constraints

• $1 \leq N \leq 1000$
• $1 \leq a_i \leq N$
• All inputs are integers.

Sample Explanation 1

There is only $ 1 $ way to divide $ 1 $ person into teams.

Sample Explanation 2

The valid team divisions that satisfy the conditions are: $((1),(2),(3)),\ ((1,2),(3)),\ ((1,3),(2)),\ ((2,3),(1))$, which totals $ 4 $ ways.

见题面 Input 部分

见题面 Output 部分