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 <= 10^{12}). Next line will contain N integers, value of the coins which will be positive and less than or equal to **10 ^{9}**.

### 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 |