TopCoder

User's AC Ratio

100.0% (28/28)

Submission's AC Ratio

44.3% (51/115)

Description

相信大家都知道,現在流通於市面的新台幣面額常見的有1, 5, 10, 50, 100, 500, 1000。(20、200、2000元和五角並不常見)
假設過了幾百年以後,央行發行了「新新台幣」,有N種面額,分別是1, 5, 10, 50, ...如此下去的規律,請計算給定的新台幣們能湊出的不為零的金額數有多少個。

Input Format

第一行有一個正整數$1\leq N\leq 19$,代表使用的新台幣面額個數。
第二行有$N$個正整數$0\leq c_i\leq 10^ 9$,代表現在有$c_i$個第$i$種新台幣。
以下以$S$代表$c_1+\dots+c_N$

子任務(測資) 額外限制 分數
1 (0~4) $c_i < 2$ 7
2 (5~9) $S\leq 20$ 11
3 (10~14) $N\leq 7, S\leq 1000$ 16
4(10~19) $N\leq 8, S\leq 2000$ 17
5 (0~24) 無限制 49

Output Format

輸出一個整數,代表能湊出的不為零的金額個數。請將答案模1000000007後輸出。

Sample Input

4
7 0 6 1

Sample Output

95

Hints

有7個1塊,6個10塊,1個50塊,能湊出1~7,10~17,20~27,30~37,40~47,50~57,60~67,70~77,80~87,90~97,100~107,110~117共95種非零金額。

Problem Source

Problem set / Description by Paupière
題目取自2015 TOI第一階段選訓第二次模擬考pA

Subtasks

No. Testdata Range Score
1 0~4 7
2 5~9 11
3 10~14 16
4 10~19 17
5 0~24 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 5
1 1000 65536 262144 1 5
2 1000 65536 262144 1 5
3 1000 65536 262144 1 5
4 1000 65536 262144 1 5
5 1000 65536 262144 2 5
6 1000 65536 262144 2 5
7 1000 65536 262144 2 5
8 1000 65536 262144 2 5
9 1000 65536 262144 2 5
10 1100 65536 262144 3 4 5
11 1000 65536 262144 3 4 5
12 1000 65536 262144 3 4 5
13 1000 65536 262144 3 4 5
14 1000 65536 262144 3 4 5
15 1500 65536 262144 4 5
16 1500 65536 262144 4 5
17 1500 65536 262144 4 5
18 1500 65536 262144 4 5
19 1500 65536 262144 4 5
20 1000 65536 262144 5
21 1000 65536 262144 5
22 1000 65536 262144 5
23 1000 65536 262144 5
24 1000 65536 262144 5