BZPRO
#4588. CoinChange
内存限制：128 MiB
时间限制：1 Sec
提交
提交记录
讨论
题目描述
Claris王国有n种货币，每种货币有一个价值vi，并且满足任意两种货币的价值成倍数关系。
即对于第i种货币和第j种货币，有vi整除vj，或者vj整除vi。
现在给出这n种货币的价值，请你计算有多少种方案能凑出价值为m的货币组合。
假设每种货币的数量是无限的，货币的价值互不相同。
为了保证有解，我们约定存在一种货币的价值为1。
由于答案可能很大，你只需要给出答案对10^9+7取模的值。
输入格式
对于每组数据：
第一行两个正整数n和m。
第二行n个正整数，表示n种货币的价值，保证货币的价值是按照升序给出的。
每组数据有n<=40, m<=10^18, vi<=10^18。
不超过300组数据。
输出格式
样例
样例输入
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。
数据范围与提示
BZPRO