Коробки
Дано 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 не є рішеннями, оскільки ми все ще можемо розмістити ще одну коробку.