Claris王国有n种货币,每种货币有一个价值vi,并且满足任意两种货币的价值成倍数关系.
即对于第i种货币和第j种货币,有vi整除vj,或者vj整除vi.
现在给出这n种货币的价值,请你计算有多少种方案能凑出价值为m的货币组合.
假设每种货币的数量是无限的,货币的价值互不相同.
为了保证有解,我们约定存在一种货币的价值为1.
由于答案可能很大,你只需要给出答案对10^9+7取模的值.
第二行n个正整数,表示n种货币的价值,保证货币的价值是按照升序给出的.
每组数据有n<=40 m<=10^18 vi<=10^18.
不超过300组数据.
对于第一组样例,两种方案分别为1+1+1+1和1+3.
对于第二组样例,四种方案分别为1+1+1+1和1+1+2和2+2和4.