#3135. CoinChange

CoinChange

Description

Claris王国有n种货币,每种货币有一个价值vi,并且满足任意两种货币的价值成倍数关系。

即对于第i种货币和第j种货币,有vi整除vj,或者vj整除vi。

现在给出这n种货币的价值,请你计算有多少种方案能凑出价值为m的货币组合。

假设每种货币的数量是无限的,货币的价值互不相同。

为了保证有解,我们约定存在一种货币的价值为1。

由于答案可能很大,你只需要给出答案对10^9+7取模的值。

Format

Input

对于每组数据:

第一行两个正整数n和m。

第二行n个正整数,表示n种货币的价值,保证货币的价值是按照升序给出的。

每组数据有n<=40, m<=10^18, vi<=10^18。

不超过300组数据。

Output

Samples

2 4
1 3
3 4
1 2 4
2
4
Hint
对于第一组样例,两种方案分别为1+1+1+1和1+3。
对于第二组样例,四种方案分别为1+1+1+1和1+1+2和2+2和4。