3008. Coins (I)

单点时限: 1.0 sec

内存限制: 256 MB

In a strange shop there are $n$ types of coins of value $A_1, A_2, \ldots, A_n$. You have to find the number of ways you can make $K$ using the coins. You can use any coin at most $K$ times.

For example, suppose there are three coins $1, 2, 5$. Then if $K = 5$ the possible ways are:

  • 11111
  • 1112
  • 122
  • 5

So, 5 can be made in 4 ways.

输入格式

Input starts with an integer $T$ ($T \le 20$), denoting the number of test cases.

Each case starts with a line containing two integers $n$ ($1 \le n \le 100$) and $K$ ($1 \le K \le 100~000$). The next line contains $n$ integers, denoting $A_1, A_2, \ldots, A_n$ ($1 \le A_i \le 100~000$). All $A_i$ will be distinct.

输出格式

For each case, print the case number and the number of ways $K$ can be made. Result can be large, so, print the result modulo $100~000~007$.

样例

Input
2
3 5
1 2 5
4 20
1 2 3 4
Output
Case 1: 4
Case 2: 108

71 人解决,81 人已尝试。

100 份提交通过,共有 371 份提交。

3.5 EMB 奖励。

创建: 11 年,1 月前.

修改: 7 年前.

最后提交: 3 月前.

来源: Coins 系列

题目标签
DP