No.137 貯金箱の焦り

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 32
作問者 : hos.lyrichos.lyric
23 ProblemId : 192 / 出題時の順位表
問題文最終更新日: 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$ 枚
の $4$ 通りあります.

サンプル2
入力
2 2015
47 53
出力
0

ちょうど $M$ 円を支払うことは不可能かもしれません.

サンプル3
入力
4 1000000000000000000
5 8 58 85
出力
48489055

$1{,}234{,}567{,}891$ で割った余りをとることをお忘れなく.

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。