题目描述

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。

提示

没有写明提示

题目来源

Topcoder SRM 527 Div1 Hard P8XCoinChange By Tangjz