박스

너비가 $w_1, w_2, \dots, w_n$인 박스 $n$개와 너비가 $W$인 큰 박스가 있다. 박스를 큰 박스에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

조건은 다음과 같다.

1. 큰 박스에 넣은 박스의 너비의 합은 $W$보다 크면 안 된다.
2. 박스는 큰 박스의 가장 왼쪽부터 하나씩 넣으며, 박스 사이에 빈 공간이 있으면 안 된다. 큰 박스의 오른쪽에는 빈 공간이 남을 수 있지만, 그 공간에 들어갈 수 있으면서 아직 넣지 않은 박스가 있으면 안 된다.
3. 한 방법에서 어떤 박스가 $i$번째에 있는데 다른 방법에서 그 박스가 다른 위치에 있다면, 두 방법은 서로 다른 방법이다.
4. 너비가 같은 두 박스는 서로 구분할 수 없다.

첫째 줄에 테스트 케이스의 개수 $T$ ($T \le 100$)가 주어진다.

각 테스트 케이스의 첫째 줄에 $n$ ($1 \le n \le 100$)과 $W$ ($1 \le W \le 1000$)가 주어진다. 둘째 줄에 박스의 너비 $w_1, w_2, \dots, w_n$이 주어진다. ($1 \le w_i \le W$)

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 방법의 수를 $10007$로 나눈 나머지이다.

$n = 3$, $W = 5$이고 너비가 $1, 2, 3$인 경우 가능한 방법은 다음 여섯 가지이다. 각 줄은 왼쪽부터 넣은 박스의 너비를 순서대로 적은 것이다.

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

박스를 하나만 넣는 1, 2, 3은 모두 2번 조건에 걸린다. 오른쪽 빈 공간에 들어갈 수 있는 박스가 아직 남아 있기 때문이다.