3008. Coins (I)

单点时限: 1.0 sec

内存限制: 256 MB

In a strange shop there are types of coins of value . You have to find the number of ways you can make using the coins. You can use any coin at most times.

For example, suppose there are three coins . Then if the possible ways are:

  • 11111
  • 1112
  • 122
  • 5

So, 5 can be made in 4 ways.

输入格式

Input starts with an integer (), denoting the number of test cases.

Each case starts with a line containing two integers () and (). The next line contains integers, denoting (). All will be distinct.

输出格式

For each case, print the case number and the number of ways can be made. Result can be large, so, print the result modulo .

样例

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

48 人解决,56 人已尝试。

71 份提交通过,共有 195 份提交。

3.7 EMB 奖励。

创建: 6 年,5 月前.

修改: 2 年,3 月前.

最后提交: 1 周,6 天前.

来源: Coins 系列

题目标签
DP