問題文
在高桥君的国家,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 注意,不包括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 的余数。