Description

A thief made his way to a shop.

There are n kinds of products in the shop and an infinite number of products of each kind. The value of one product of kind $i$ is $a_i$.

The thief wonders how many way to take some products such that the value of them is exactly $k$ (it's possible for some kinds to take several products of that kind).

Find the answer modulo $10^9+7$.

Format

Input

The first line of the input gives the number of test cases, $T(1≤T≤100)$. $T$ test cases follow.

For each test case, the first line contains two integers $n,k(1≤n≤100,1≤k≤10^18)$, the number of kinds of products and the value of products the thief will take.

The second line contains $n$ integers $a_i(1≤a_i≤10)$ — the values of products for kinds from $1$ to $n$.

It is guaranteed that there are no more than 10 testcases with $n>50$.

It is guaranteed that there are no more than 40 testcases with $n>20$.

It is guaranteed that there are no more than 80 testcases with $n>10$.

Output

For each test case, print a line with an integer, representing the answer, modulo $10^9+7$.

Samples

5
4 10
1 2 5 10
4 100
1 2 5 10
5 20
1 1 1 1 1
10 1000000000000
1 2 3 4 5 6 7 8 9 10
20 1000000000000000000
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10

11
2156
10626
321553432
822368450