No.137 貯金箱の焦り
問題文最終更新日: 2015-11-14 17:47:08
問題文
貯金箱さんは A 国に住んでいます.この国では通貨の単位は円と呼ばれ,$A_1$ 円玉,$A_2$ 円玉,…,$A_N$ 円玉の,$N$ 種類の硬貨が使われています.
貯金箱さんは硬貨を貯めに貯めて,どの硬貨も $10^{100}$ 枚持っています.あるとき,貯金箱さんは $M$ 円の買い物をすることになりました.ところが,「わたしの持っている硬貨でちょうど $M$ 円を支払う方法は何通りだろう?」とふと疑問に思ってしまい,気になって買い物ができず困っています.
貯金箱さんが硬貨でちょうど $M$ 円を支払う方法の個数を $1{,}234{,}567{,}891$ で割った余りを求めるプログラムを書いてください.$2$ つの支払い方が同じであるとは,どの種類の硬貨も同じ枚数使うこととします.
入力
$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$
- 入力の値はすべて整数.
- $1 \le N \le 50$.
- $1 \le M \le 10^{18}$.
- $1 \le A_1 < A_2 < \cdots < A_N \le 500$.
出力
貯金箱さんが硬貨でちょうど $M$ 円を支払う方法の個数を $1{,}234{,}567{,}891$ で割った余りを $1$ 行に出力してください.
サンプル
サンプル1
入力
6 13 1 5 10 50 100 500
出力
4
$13$ 円の支払い方には,
- $1$ 円玉 $13$ 枚
- $1$ 円玉 $8$ 枚と $5$ 円玉 $1$ 枚
- $1$ 円玉 $3$ 枚と $5$ 円玉 $2$ 枚
- $1$ 円玉 $3$ 枚と $10$ 円玉 $1$ 枚
サンプル2
入力
2 2015 47 53
出力
0
ちょうど $M$ 円を支払うことは不可能かもしれません.
サンプル3
入力
4 1000000000000000000 5 8 58 85
出力
48489055
$1{,}234{,}567{,}891$ で割った余りをとることをお忘れなく.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。