Given \textbf{n} boxes with widths of \textbf{w_1}, \textbf{w_2}, ..., \textbf{w_n} and another big box with width \textbf{W}, find how many ways the boxes can be put in the big box. The constrains are: \begin{enumerate} \item Of course the summation of widths of the placed boxes should not be greater than \textbf{W}. \item 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). \item Two orderings are considered different if in one ordering, one box is in \textbf{i}^th position, but in another ordering, it isn’t. \item If two boxes have same widths, they should be considered same. \end{enumerate} \InputFile Input starts with an integer \textbf{T} (≤ \textbf{100}), denoting the number of test cases. Each case starts two integers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}) and \textbf{W} (\textbf{1} ≤ \textbf{W} ≤ \textbf{1000}). The next line contains \textbf{n} space separated integers, denoting \textbf{w_1} \textbf{w_2} ... \textbf{w_n} (\textbf{1} ≤ \textbf{w_i} ≤ \textbf{W}). \OutputFile For each case, print the case number first and the result modulo \textbf{10007}. \textbf{Notes} For the first case, the orderings are \textbf{1 2} \textbf{1 3} \textbf{2 1} \textbf{2 3} \textbf{3 1} \textbf{3 2} Only \textbf{1} or \textbf{2} or \textbf{3} is not solutions since we can still place another box.