Коробки
Дано n коробок с ширинами w_1, w_2, ..., w_n и одна большая коробка с шириной W. Определите, сколькими способами можно разместить эти коробки внутри большой коробки. Условия:
Суммарная ширина размещенных коробок не должна превышать W.
Коробки должны быть размещены последовательно, начиная с левой стороны, без промежутков между ними. Таким образом, конец большой коробки может остаться пустым. Однако, если есть неразмещенная коробка, которая может поместиться в оставшееся пространство, такое расположение считается недопустимым (см. объяснение для примера 1).
Два расположения считаются различными, если в одном из них какая-либо коробка находится на i-й позиции, а в другом — нет.
Коробки с одинаковыми ширинами считаются идентичными.
Входные данные
Ввод начинается с целого числа T (≤ 100), обозначающего количество тестов.
Каждый тест начинается с двух целых чисел n (1 ≤ n ≤ 100) и W (1 ≤ W ≤ 1000). Следующая строка содержит n целых чисел, разделенных пробелами, которые обозначают w_1 w_2 ... w_n (1 ≤ w_i ≤ W).
Выходные данные
Для каждого теста выведите номер теста и результат по модулю 10007.
Примечания
Для первого теста возможные расположения:
1 2
1 3
2 1
2 3
3 1
3 2
Только 1, 2 или 3 не являются решениями, так как можно разместить еще одну коробку.