Description

Xiao Z wants to take a class photo, so he needs everyone to line up first. He wants them to stand in $k$ rows, and he specifies the number of people in each row, ensuring that each row has no more people than the row behind it.

He then finds the lineup still looks messy because all heights are different. So he wants the row heads to be aligned (left-justified), and each student must be shorter than both the student directly behind them and the student toward the direction of the row head (if such students exist).

After arranging, the thoughtful Xiao Z wants to know how many different lineups there are.

For example, if everyone stands in $3$ rows, and the row sizes from back to front are $3$, $2$, $1$, there are the following $16$ lineups (each number represents the rank of a student when all students are sorted by height 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 Xiao Z cannot compute it, so he asks you for help.

Input Format

The first line contains an integer $k$.

The second line contains $k$ integers, giving the number of people in each row from back to front.

Output Format

One line containing an integer, the number of possible lineups.

3
3 2 1

16

5
1 1 1 1 1 

1

Hint

Constraints

• For $30\%$ of the testdata, $n \le 10$.
• For another $30\%$ of the testdata, only the last row has more than $1$ person.
• For $100\%$ of the testdata, $1 \le k \le 5$, $1 \le n \le 30$, and the number of lineups is less than $2^{32}$.

Translated by ChatGPT 5