P5286 - Another thief in a Shop

内存限制：128 MB 时间限制：12.000 S

评测方式：文本比较命题人：

提交：3 解决：1

提交提交记录统计侧边提交

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

ai.
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⁹+7.

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¹⁸), the number of kinds of products and the value of products the thief will take.

The second line contains

n integers

ai(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.

For each test case, print a line with an integer, representing the answer, modulo

10⁹+7.

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

5286: Another thief in a Shop