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。