Problem Statement

Chokinbako lives in Country A. In this country, the unit of currency is called the yen, and $N$ kinds of coins are in use: $A_1$-yen coins, $A_2$-yen coins, …, $A_N$-yen coins.

Chokinbako has saved up coins over and over and now has $10^{100}$ coins of every kind. One day, Chokinbako is about to make a purchase of $M$ yen. However, the question "In how many ways can I pay exactly $M$ yen with the coins I have?" suddenly came to mind, and Chokinbako is too bothered by it to make the purchase.

Write a program that finds the number of ways for Chokinbako to pay exactly $M$ yen with coins, modulo $1{,}234{,}567{,}891$. $2$ ways of paying are considered the same if they use the same number of coins of every kind.

Input

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$

• All input values are integers.
• $1 \le N \le 50$.
• $1 \le M \le 10^{18}$.
• $1 \le A_1 < A_2 < \cdots < A_N \le 500$.

Output

Output on $1$ line the number of ways for Chokinbako to pay exactly $M$ yen with coins, modulo $1{,}234{,}567{,}891$.

Sample

6 13
1 5 10 50 100 500

4

2 2015
47 53

0

4 1000000000000000000
5 8 58 85

48489055