UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4588. CoinChange

统计 下载数据

Description

Claris王国有n种货币,每种货币有一个价值vi,并且满足任意两种货币的价值成倍数关系。
即对于第i种货币和第j种货币,有vi整除vj,或者vj整除vi。
现在给出这n种货币的价值,请你计算有多少种方案能凑出价值为m的货币组合。
假设每种货币的数量是无限的,货币的价值互不相同。
为了保证有解,我们约定存在一种货币的价值为1。
由于答案可能很大,你只需要给出答案对10^9+7取模的值。

Input

对于每组数据:
第一行两个正整数n和m。
第二行n个正整数,表示n种货币的价值,保证货币的价值是按照升序给出的。
每组数据有n<=40, m<=10^18, vi<=10^18。
不超过300组数据。

Output

Sample Input

2 4
1 3
3 4
1 2 4

Sample Output

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

Hint

Source

Topcoder SRM 527 Div1 Hard P8XCoinChange By Tangjz