D - お釣りの嫌いな高橋君

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君の国では、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