#codeformula2014qualBd. [code_formula_2014_qualB_d]お釣りの嫌いな高橋君

[code_formula_2014_qualB_d]お釣りの嫌いな高橋君

問題文

高橋君の国では、NN 種類の硬貨が使われています。 11 番目の硬貨の価値は 11 円です。 kk 番目の硬貨の価値は、k1k-1 番目の硬貨の 1010 倍あります。 つまり、22 番目の硬貨は 1010 円の価値があり、55 番目の硬貨は 1000010000 円の価値があります。

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

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


入力

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

NN A1A_1 A2A_2 : ANA_N

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

出力

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


入力例1


2
2
1

出力例1


5

払える金額は、11 円, 22 円, 1010 円, 1111 円, 1212 円の 55 通りとなります。

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


入力例2


2
32
3

出力例2


62

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


入力例3


4
12
3
7
34

出力例3


12039

入力例4


10
1234
2
857
3858
1
5000
32
4
1
857

出力例4


969347336

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


Source Name

Code Formula 2014 予選B