Problem Description

In Takahashi's country, $ N $ types of coins are used. The value of the $ 1 $st coin is $ 1 $ yen. The value of the $ k $th coin is $ 10 $ times the value of the $ (k-1) $th coin. That is, the $ 2 $nd coin has a value of $ 10 $ yen, and the $ 5 $th coin has a value of $ 10000 $ yen.

Takahashi hates change. Therefore, he wants to shop as much as possible with the exact amount. Takahashi wants to find out how many different amounts he can pay with the coins he currently has.

Output the number of different amounts Takahashi can pay. However, since this number can be enormous, output the remainder when divided by $ 1000000007 $.

Input Format

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

$ N $ $ A_1 $ $ A_2 $ : $ A_N $

• The first line contains the number of coin types $N\ (1\ ≦\ N\ ≦\ 50)$.
• The next $ N $ lines contain the number of coins Takahashi has for each type. The $ i(1≦i≦N) $th line contains an integer $ A_i(0≦A_i≦50000) $, which represents the number of $ i $th coins Takahashi has.

Output Format

Output the number of different amounts Takahashi can pay, modulo $ 1000000007 $. The output should be in one line with a newline at the end.

Sample Input and Output

Sample Input #1

2
2
1

Sample Output #1

5

Sample Input #2

2
32
3

Sample Output #2

62

Sample Input #3

4
12
3
7
34

Sample Output #3

12039

Sample Input #4

10
1234
2
857
3858
1
5000
32
4
1
857

Sample Output #4

969347336

Notes/Hints

Sample Explanation 1

The amounts that can be paid are $ 1 $ yen, $ 2 $ yen, $ 10 $ yen, $ 11 $ yen, and $ 12 $ yen, totaling $ 5 $ different amounts. Note that $ 0 $ yen is not included.

Sample Explanation 2

Takahashi can pay $ 62 $ different amounts from $ 1 $ yen to $ 62 $ yen.

Sample Explanation 4

Output the remainder when divided by $ 1000000007 $.

见题面 Input 部分

见题面 Output 部分