시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 33 10 6 21.429%

문제

너비가 w1, w2, ..., wn인 박스 n개와 너비가 W인 큰 박스가 주어졌을 때, 박스를 큰 박스에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

조건은 다음과 같다.

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

입력

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

각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100)과 W (1 ≤ W ≤ 1000)가 주어진다. 둘째 줄에는 w1, w2, ..., wn이 주어진다. (1 ≤ wi ≤ W)

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고, 방법의 수를 10007로 나눈 나머지를 출력한다.

예제 입력

2
3 5
1 2 3
5 10
1 2 2 4 5

예제 출력

Case 1: 6
Case 2: 30

힌트

첫 번째 테스트 케이스의 경우에 가능한 방법은 다음과 같다.

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

1, 2, 또는 3과 같이 박스를 하나만 넣는 경우는 불가능하다. (2번 조건)