BUD13TLF  Boxes
Given n boxes with widths of w1, w2, . . . , wn and another big box with width W, find how many ways the boxes can be put in the big box. The constrains are:
1) Of course the summation of widths of the placed boxes should not be greater than W.
2) The boxes should be placed one by one starting from left without leaving any empty spaces between them. So, the end of the big box may contain empty spaces. But if there is any unplaced box which can be fit in this space, the ordering should be considered invalid (See the explanation for sample case 1).
3) Two orderings are considered different if in one ordering, one box is in ith position, but in another ordering, it isn’t.
4) If two boxes have same widths, they should be considered same
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts two integers n (1 ≤ n ≤ 100) and W (1 ≤ W ≤ 1000). The next line contains n space separated integers, denoting w1 w2 . . . wn (1 ≤ wi ≤ W).
Output
For each case, print the case number first and the result modulo 10007.
Example
Input: 2 3 5 1 2 3 5 10 1 2 2 4 5 Output: Case 1: 6 Case 2: 30 Notes: For the first case of the Sample Input, the orderings are 12 13 21 23 31 32 Only 1 or 2 or 3 is not solutions since we can still place another box.
hide comments
kshubham02:
20170823 07:53:53
Does putting no boxes in the larger box count as an ordering?


Alex Anderson:
20151030 07:05:01
Also, I think the cases are too easy relative to the constraints. I think my solution is probably a factor of O(n) too slow, but maybe I optimized enough. Last edit: 20151030 07:05:11 

Alex Anderson:
20151030 06:04:09
Can you fix the way the sample input and output is displayed? It is difficult to read. 
Added by:  Gầy :)) 
Date:  20151027 
Time limit:  1s15s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  The 2013 ACMICPC Asia Phuket Regional Programming Contest 