← 返回题目列表

AtCoder · code_formula_2014_qualB_d

D. 高桥讨厌换钱

中文机器翻译题面 查看原题

問題文

在高桥君的国家,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 的余数。