問題文

高橋君の国では、$N$ 種類の硬貨が使われています。 $1$ 番目の硬貨の価値は $1$ 円です。 $k$ 番目の硬貨の価値は、$k-1$ 番目の硬貨の $10$ 倍あります。 つまり、$2$ 番目の硬貨は $10$ 円の価値があり、$5$ 番目の硬貨は $10000$ 円の価値があります。

高橋君は、お釣りが嫌いです。なので、出来るだけぴったりの金額で買い物がしたいと思っています。 そこで高橋君は、今持っている硬貨で、何種類の金額が払えるかを調べたいと思いました。

高橋君が払える金額が何通りあるかを出力しなさい。 ただし、これは膨大な数となるため、 $1000000007$ 以上となる場合は、 $1000000007$ で割った余りを出力しなさい。

入力

入力は以下の形式で標準入力から与えられる。

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

• $1$ 行目には、硬貨の種類数 $N (1 ≦ N ≦ 50)$ が、$1$ 行で与えられる。
• $2$ 行目から $N$ 行では、高橋君が各硬貨を何枚持っているかが与えられる。 このうち $i(1≦i≦N)$ 行目では、 $i$ 番目の硬貨を、高橋君が何枚持っているかを表す整数 $A_i(0≦A_i≦50000)$が与えられる。

出力

高橋君が払える金額の種類数を、 $1000000007$ で割った余りを $1$ 行で出力せよ。出力の末尾は改行をいれること。

入力例1

2
2
1

出力例1

5

払える金額は、$1$ 円, $2$ 円, $10$ 円, $11$ 円, $12$ 円の $5$ 通りとなります。

$0$ 円は含まないことに注意してください。

入力例2

2
32
3

出力例2

62

$1$ 円から $62$ 円の $62$ 通りの金額を支払うことが出来ます。

入力例3

4
12
3
7
34

出力例3

12039

入力例4

10
1234
2
857
3858
1
5000
32
4
1
857

出力例4

969347336

$1000000007$ で割った余りを出力してください。

Source Name

Code Formula 2014 予選B