F. Coin Change

Score: 1

CPU: 2s
Memory: 1024MB

Given N coins, find out how many permutations of the coins have a prefix (possibly empty) whose sum is equal to K. All the coins are considered different even if they have the same value. For example, given coins 1, 2, 3, 3, 6 (N = 5) and K = 5 the permutations we are looking for are given below. For better understanding, the first 3 is denoted by 3a and second three is denoted by 3b.

2 3b 1 3a 6 2 3a 1 3b 6 3a 2 1 3b 6 3b 2 1 3a 6
2 3b 1 6 3a 2 3a 1 6 3b 3a 2 1 6 3b 3b 2 1 6 3a
2 3b 3a 1 6 2 3a 3b 1 6 3a 2 3b 1 6 3b 2 3a 1 6
2 3b 3a 6 1 2 3a 3b 6 1 3a 2 3b 6 1 3b 2 3a 6 1
2 3b 6 1 3a 2 3a 6 1 3b 3a 2 6 1 3b 3b 2 6 1 3a
2 3b 6 3a 1 2 3a 6 3b 1 3a 2 6 3b 1 3b 2 6 3a 1

Here, two coins with value 3 are considered different. Prefixes with sum = K are underlined. So in this case the result will be 24.

Input

First line, T (T <= 100), number of test cases. Each case will start with N (0 <= N <= 32) and K (0 <= K <= 1012). Next line will contain N integers, value of the coins which will be positive and less than or equal to 109.

Output

For each case, output one line: “Case C: A”, where C is the case number and A is the answer for the case modulo 1,000,000,007.

Sample

Input Output
2
5 5
1 2 3 3 6
5 6
1 2 3 3 6
Case 1: 24
Case 2: 60