问题描述

在高桥君的国家，有 $N$ 种硬币。第一种硬币的价值是 1 日元。第 $k$ 种硬币的价值是第 $k-1$ 种硬币的 10 倍。也就是说，第二种硬币的价值是 10 日元，第五种硬币的价值是 10000 日元。

高桥君不喜欢零钱。所以，他想尽量用准确的金额购物。因此，高桥君想要用他现有的硬币，确定能支付多少种金额。

请输出高桥君能支付的金额的种类数。注意，这个数字非常大，如果超过 $1000000007$，请输出余数为 $1000000007$。

输入

输入以以下格式从标准输入中给出。

$N$ $A_1$ $A_2$ : $A_N$

• 第一行是硬币的种类数 $N (1 \leq N \leq 50)$。
• 第二行到第 $N$ 行是高桥君持有的每种硬币的数量。其中第 $i(1 \leq i \leq N)$ 行表示高桥君持有第 $i$ 种硬币的数量 $A_i(0 \leq A_i \leq 50000)$。

输出

用一行输出高桥君能支付的金额的种类数，取余数为 $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$。

来源

Code Formula 2014 预选B