시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 42 12 7 23.333%

문제

너비가 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로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

Case 1: 6
Case 2: 30

힌트

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

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

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

W3sicHJvYmxlbV9pZCI6Ijk2MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTVcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjEwOFx1YmU0NFx1YWMwMCB3PHN1Yj4xPFwvc3ViPiwgdzxzdWI+MjxcL3N1Yj4sIC4uLiwgdzxzdWI+bjxcL3N1Yj5cdWM3NzggXHViYzE1XHVjMmE0IG5cdWFjMWNcdWM2NDAgXHViMTA4XHViZTQ0XHVhYzAwIFdcdWM3NzggXHVkMDcwIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJjMTVcdWMyYTRcdWI5N2MgXHVkMDcwIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWIxMjNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjODcwXHVhYzc0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVkMDcwIFx1YmMxNVx1YzJhNFx1YzU0OFx1YzVkMCBcdWJjMTVcdWMyYTRcdWM3NTggXHViMTA4XHViZTQ0XHVjNzU4IFx1ZDU2OVx1Yzc0MCBXXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmMxNVx1YzJhNFx1YjI5NCBcdWQwNzAgXHViYzE1XHVjMmE0XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjEyM1x1YzczY1x1YmE3MCwgXHViYzE1XHVjMmE0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1ZDA3MCBcdWJjMTVcdWMyYTRcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3NzQgXHVjMGRkXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjNzc0IFx1YWNmNVx1YWMwNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NFx1YzExYyBcdWM1NDRcdWM5YzEgXHVkMDcwIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWIxMjNcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQ1NWMgXHViYzI5XHViYzk1XHVjNWQwXHVjMTFjIFx1YzViNFx1YjVhNCBcdWJjMTVcdWMyYTRcdWFjMDAgaVx1YmM4OFx1YzlmOFx1YzVkMCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM1ZDBcdWMxMWMgXHVhZGY4IFx1YmMxNVx1YzJhNFx1YWMwMCBcdWIyZTRcdWI5NzggXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHViNDUwIFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViMTA4XHViZTQ0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWQ2Y1x1YmQ4NFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKCZsZTsgMTAwKVx1YWMwMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuICgxICZsZTsgbiAmbGU7IDEwMClcdWFjZmMgVyAoMSAmbGU7IFcgJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgdzxzdWI+MTxcL3N1Yj4sIHc8c3ViPjI8XC9zdWI+LCAuLi4sIHc8c3ViPm48XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB3PHN1Yj5pPFwvc3ViPiAmbGU7IFcpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEwMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIDI8XC9saT5cclxuXHQ8bGk+MSAzPFwvbGk+XHJcblx0PGxpPjIgMTxcL2xpPlxyXG5cdDxsaT4yIDM8XC9saT5cclxuXHQ8bGk+MyAxPFwvbGk+XHJcblx0PGxpPjMgMjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjEsIDIsIFx1YjYxMFx1YjI5NCAzXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJjMTVcdWMyYTRcdWI5N2MgXHVkNTU4XHViMDk4XHViOWNjIFx1YjEyM1x1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LiAoMlx1YmM4OCBcdWM4NzBcdWFjNzQpPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NjE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQm94ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIG4gYm94ZXMgd2l0aCB3aWR0aHMgb2YgdzxzdWI+MTxcL3N1Yj4sIHc8c3ViPjI8XC9zdWI+LCAuLi4sIHc8c3ViPm48XC9zdWI+IGFuZCBhbm90aGVyIGJpZyBib3ggd2l0aCB3aWR0aCBXLCBmaW5kIGhvdyBtYW55IHdheXMgdGhlIGJveGVzIGNhbiBiZSBwdXQgaW4gdGhlIGJpZyBib3guIFRoZSBjb25zdHJhaW5zIGFyZTombmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5PZiBjb3Vyc2UgdGhlIHN1bW1hdGlvbiBvZiB3aWR0aHMgb2YgdGhlIHBsYWNlZCBib3hlcyBzaG91bGQgbm90IGJlIGdyZWF0ZXIgdGhhbiBXLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgYm94ZXMgc2hvdWxkIGJlIHBsYWNlZCBvbmUgYnkgb25lIHN0YXJ0aW5nIGZyb20gbGVmdCB3aXRob3V0IGxlYXZpbmcgYW55IGVtcHR5IHNwYWNlcyBiZXR3ZWVuIHRoZW0uIFNvLCB0aGUgZW5kIG9mIHRoZSBiaWcgYm94IG1heSBjb250YWluIGVtcHR5IHNwYWNlcy4gQnV0IGlmIHRoZXJlIGlzIGFueSB1bnBsYWNlZCBib3ggd2hpY2ggY2FuIGJlIGZpdCBpbiB0aGlzIHNwYWNlLCB0aGUgb3JkZXJpbmcgc2hvdWxkIGJlIGNvbnNpZGVyZWQgaW52YWxpZCAoU2VlIHRoZSBleHBsYW5hdGlvbiBmb3Igc2FtcGxlIGNhc2UgMSkuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlR3byBvcmRlcmluZ3MgYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50IGlmIGluIG9uZSBvcmRlcmluZywgb25lIGJveCBpcyBpbiBpPHN1cD50aDxcL3N1cD4gcG9zaXRpb24sIGJ1dCBpbiBhbm90aGVyIG9yZGVyaW5nLCBpdCBpc24mcnNxdW87dC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgdHdvIGJveGVzIGhhdmUgc2FtZSB3aWR0aHMsIHRoZXkgc2hvdWxkIGJlIGNvbnNpZGVyZWQgc2FtZS4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgc3RhcnRzIHdpdGggYW4gaW50ZWdlciBUICgmbGU7IDEwMCksIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBjYXNlIHN0YXJ0cyB0d28gaW50ZWdlcnMgbiAoMSAmbGU7IG4gJmxlOyAxMDApIGFuZCBXICgxICZsZTsgVyAmbGU7IDEwMDApLiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIG4gc3BhY2Ugc2VwYXJhdGVkIGludGVnZXJzLCBkZW5vdGluZyB3PHN1Yj4xPFwvc3ViPiB3PHN1Yj4yPFwvc3ViPiAuLi4gdzxzdWI+bjxcL3N1Yj4gKDEgJmxlOyB3PHN1Yj5pPFwvc3ViPiAmbGU7IFcpLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIHByaW50IHRoZSBjYXNlIG51bWJlciBmaXJzdCBhbmQgdGhlIHJlc3VsdCBtb2R1bG8gMTAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkZvciB0aGUgZmlyc3QgY2FzZSwgdGhlIG9yZGVyaW5ncyBhcmUmbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIDImbmJzcDs8XC9saT5cclxuXHQ8bGk+MSAzJm5ic3A7PFwvbGk+XHJcblx0PGxpPjIgMSZuYnNwOzxcL2xpPlxyXG5cdDxsaT4yIDMmbmJzcDs8XC9saT5cclxuXHQ8bGk+MyAxJm5ic3A7PFwvbGk+XHJcblx0PGxpPjMgMiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk9ubHkgMSBvciAyIG9yIDMgaXMgbm90IHNvbHV0aW9ucyBzaW5jZSB3ZSBjYW4gc3RpbGwgcGxhY2UgYW5vdGhlciBib3guJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=