6953：Another thief in a Shop

题目描述

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\).

输入解释

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

For each test case, the first line contains two integers \(n, k(1\le n\le 100,1\le k\le 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\le a_i\le 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^9+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

输出样例

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2021“MINIEYE杯”中国大学生算法设计超级联赛（1）

源链接： HDU-6953

最后修改于 2021-10-23T19:10:48+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
4000/2000MS(Java/Others)	262144/262144K(Java/Others)