Candy Store

Interview

Time limit1sMemory limit256 MB

Summary

Count the subsets of candy prices whose total is at least C for each test case, modulo 65537.

Level: Medium4 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Anne likes candy and wants to buy some at the candy store in her neighborhood. She happens to have plenty of money, so she can buy as much candy as she wants. She wants to spend at least $C$ kroner on candy, and she buys at most one candy of each type.

There are many ways to spend at least $C$ kroner, so Anne wants to know how many before she buys anything. Her parents think she is too young to use a computer, so she asked you to write a program that counts the ways for her.

Anne dislikes large numbers such as 1,000,000,007, so report the number of ways modulo $65537$ .

Input

The first line contains the number of test cases $T$ . The first line of each test case contains the number of candy types $N$ and the least amount of money $C$ that Anne wants to spend. The second line contains $N$ space-separated integers $a_i$ , the price of candy type $i$ in kroner.

$0 < T \le 100$
$0 < N \le 200$
$0 < C \le 10000$
$0 < a_i \le 200$

Output

For each test case, print on its own line the number of ways Anne can buy candy worth at least $C$ kroner, modulo $65537$ .

Examples2

Example 1

Input

2
5 10
5 6 7 8 9
10 100
10 10 10 10 10 10 10 10 11 9

Expected output

26
1

Example 2
Input
```
1
1 1
1
```
Expected output
```
1
```