D - お釣りの嫌いな高橋君
Editorial
/
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 で割った余りを出力してください。