Problem Description

Little Z wants to take a group photo for his classmates, and for that, he needs to arrange them in a queue. He wants everyone to stand in \( k \) rows and has specified the number of people in each row, ensuring that the number of people in each row does not exceed the number in the row behind it.

Little Z finds that the queue still looks messy because everyone's heights are different. Therefore, he wants the front of each row to be aligned, and each student to be shorter than both the student directly behind them and the student in front of them in their row.

After arranging, the thoughtful Little Z also wants to know how many ways there are to arrange the queue.

For example, if everyone is arranged in 3 rows, with the number of people from back to front being 3, 2, and 1 respectively, there are 16 ways to arrange them (each number represents the rank of the student from tallest to shortest):

\[ \begin{matrix} 123 & 123 & 124 & 124 & 125 & 125 & 126 & 126 & 134 & 134 & 135 & 135 & 136 & 136 & 145 & 146 \\ 45 & 46 & 35 & 36 & 34 & 36 & 34 & 35 & 25 & 26 & 24 & 26 & 24 & 25 & 26 & 25 \\ 6 & 5 & 6 & 5 & 6 & 4 & 5 & 4 & 6 & 5 & 6 & 4 & 5 & 4 & 3 & 3 \end{matrix} \]

However, there are \( n \) students in the class, and Little Z cannot figure it out. He hopes you can help him.

Input Format

The first line contains an integer \( k \).

The second line contains \( k \) integers, representing the number of people in each row from back to front.

Output Format

A single line containing an integer, representing the number of ways to arrange the queue.

Sample Input and Output

Sample Input #1

3
3 2 1

Sample Output #1

16

Sample Input #2

5
1 1 1 1 1

Sample Output #2

1

Notes

Data Range and Constraints

For 30% of the data, \( n \le 10 \).

For another 30% of the data, only the last row has more than 1 person.

For 100% of the data, \( 1 \le k \le 5 \), \( 1 \le n \le 30 \), and the number of arrangements is less than \( 2^{32} \).

见题面 Input 部分

见题面 Output 部分