Pekka's Amusement

Interview

Time limit1sMemory limit1024 MB

Summary

Count the arrangements of multiset cards numbered 1..N where every card numbered k+1 appears after at least one card numbered k. Total cards up to 100.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

Recently Pekka found a new amusement. He took $A_1$ identical cards with the number 1 written on each, $A_2$ cards with the number 2, $\dots$ , $A_N$ cards with the number $N$ . He wants to know in how many ways all the cards can be arranged in a row so that in the resulting sequence, every card with the number $k+1$ is preceded by at least one card with the number $k$ , for $k>0$ . Help Pekka, please.

Input

The first line of the input contains the natural number $N$ . The second line contains $N$ space-separated natural numbers: $A_1, A_2, \dots, A_N$ . The sum of all $A_i$ does not exceed $100$ .

Output

Output the number of distinct card arrangements that satisfy the condition of the problem.

Hint

Possible arrangements in the example: 1 1 2 2, 1 2 1 2, 1 2 2 1. There are three arrangements in total.

Examples1

Example 1
Input
```
2
2 2
```
Expected output
```
3
```