問題文

貯金箱さんは 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$ 行に出力してください．

サンプル

6 13
1 5 10 50 100 500

4

2 2015
47 53

0

4 1000000000000000000
5 8 58 85

48489055