Box

There are $n$ boxes of widths $w_1, w_2, \dots, w_n$ and one big box of width $W$. Write a program that counts the ways to put the boxes into the big box.

The conditions are as follows.

1. The widths of the boxes put into the big box must not add up to more than $W$.
2. Boxes go in one at a time from the left end of the big box, and no gap may be left between two boxes. Empty space may remain at the right end of the big box, but no box that fits into that space may still be left out.
3. If a box sits in position $i$ in one way and in a different position in another way, the two ways count as different.
4. Two boxes of the same width cannot be told apart.

The first line contains the number of test cases $T$ ($T \le 100$).

The first line of each test case contains $n$ ($1 \le n \le 100$) and $W$ ($1 \le W \le 1000$). The second line contains the box widths $w_1, w_2, \dots, w_n$. ($1 \le w_i \le W$)

For each test case, print one line in the form Case x: y, where $x$ is the test case number starting from 1 and $y$ is the number of ways modulo $10007$.

For $n = 3$, $W = 5$ and widths $1, 2, 3$, these six ways are possible. Each line lists the widths of the boxes in the order they went in, starting from the left.

• 1 2
• 1 3
• 2 1
• 2 3
• 3 1
• 3 2

Putting in a single box, so 1, 2, or 3 on its own, breaks condition 2. A box that fits into the empty space on the right is still left out.