#codeformula2014qualBd. [code_formula_2014_qualB_d]お釣りの嫌いな高橋君
[code_formula_2014_qualB_d]お釣りの嫌いな高橋君
問題文
高橋君の国では、 種類の硬貨が使われています。 番目の硬貨の価値は 円です。 番目の硬貨の価値は、 番目の硬貨の 倍あります。 つまり、 番目の硬貨は 円の価値があり、 番目の硬貨は 円の価値があります。
高橋君は、お釣りが嫌いです。なので、出来るだけぴったりの金額で買い物がしたいと思っています。 そこで高橋君は、今持っている硬貨で、何種類の金額が払えるかを調べたいと思いました。
高橋君が払える金額が何通りあるかを出力しなさい。 ただし、これは膨大な数となるため、 以上となる場合は、 で割った余りを出力しなさい。
入力
入力は以下の形式で標準入力から与えられる。
:
- 行目には、硬貨の種類数 が、 行で与えられる。
- 行目から 行では、高橋君が各硬貨を何枚持っているかが与えられる。 このうち 行目では、 番目の硬貨を、高橋君が何枚持っているかを表す整数 が与えられる。
出力
高橋君が払える金額の種類数を、 で割った余りを 行で出力せよ。出力の末尾は改行をいれること。
入力例1
2
2
1
出力例1
5
払える金額は、 円, 円, 円, 円, 円の 通りとなります。
円は含まないことに注意してください。
入力例2
2
32
3
出力例2
62
円から 円の 通りの金額を支払うことが出来ます。
入力例3
4
12
3
7
34
出力例3
12039
入力例4
10
1234
2
857
3858
1
5000
32
4
1
857
出力例4
969347336
で割った余りを出力してください。
Source Name
Code Formula 2014 予選B