题目限制

1000 ms 128 M

题目描述

香蕉是一种非常受体育运动员喜欢的赛场提高能量的水果，但是也需要从能量不能过剩形成脂肪角度考虑而限制数量。每个香蕉都有一个能量值，不能一次吃太多，假设每天最多摄入能量值为K，你希望每天吃的香蕉能量值乘积恰好等于K，现在你需要计算一下有多少种吃法。

输入格式

第一行一个数D，表示有D天。

接下来2*D行，每天的数据有两行

每天的第一行两个数n和K，表示当天的香蕉数和最多能量值K。每天的第二行有n个用空格隔开的整数表示每个香蕉可以提供的能量值。

（n<=1000,K<=100000000,D<=20）

输出格式

D行，每行一个数表示方案数，输出对1000000007取模的结果。

数据范围

对于30%的数据： n,K<=100

对于60%的数据： n<=1000,K<=10000

对于100%的数据： n<=1000,K<=100000000,D<=20

输入样例

3

3 3

1 1 3

3 6

2 3 6

3 5

1 5 1

输出样例

4

2

4