問題文

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

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

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

入力例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 で割った余りを出力してください。