問題文

貯金箱さんは A 国に住んでいます．この国では通貨の単位は円と呼ばれ，$A_1$ 円玉，$A_2$ 円玉，…，$A_N$ 円玉の，$N$ 種類の硬貨が使われています．

貯金箱さんは硬貨を貯めに貯めて，どの硬貨も ${10}^{100}$ 枚持っています．あるとき，貯金箱さんは $M$ 円の買い物をすることになりました．ところが，「わたしの持っている硬貨でちょうど $M$ 円を支払う方法は何通りだろう？」とふと疑問に思ってしまい，気になって買い物ができず困っています．

貯金箱さんが硬貨でちょうど $M$ 円を支払う方法の個数を $\mathrm{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$ 円を支払う方法の個数を $\mathrm{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