F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Another thief in a Shop

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 297    Accepted Submission(s): 106


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

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

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

Sample Input
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
 

Sample Output
11 2156 10626 321553432 822368450
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 18:32:44, Gzip enabled