e-olymp
Задачі

Перестановки з даною дистанцією

Перестановки з даною дистанцією

У Батхеда є n томів його улюбленої Енциклопедії Для Нерозумних Підлітків. Томи пронумеровані від 1 до n та виставлені у ряд. Він не любить строгого порядку, але також він не любить і суцільного хаосу. Батхед розраховує дистанцію перестановки томів як суму різниць номера та позиції для всіх томів. Іншими словами, якщо перестановка має вигляд (i1, i2, ... in), де ik (1 ≤ kn) означає номер тому на k-му місці, то ії дистанція дорівнює |i1–1|+|i2–2|+...+|inn|. Улюблене число Батхеда дорівнює d, і він хоче виставити томи Енциклопедії так, щоб дистанція була рівна d. Скількома способами він може це зробити?

Вхідні дані

Перший рядок вводу містить кількість тестів T (1T100). Кожен з наступних T рядків містить дані для одного тесту: кількість томів n (1n50) і потрібну дистанцію d (0d10000), які відокремлені пропуском. Числа n, d – цілі.

Вихідні дані

Виведіть T рядків вигляду "Case #A: B", де A – номер тесту (починаючи з 1), B – кількість перестановок n томів з дистанцією d, взятих за модулем 100007.

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані
5
2 0
2 2
4 1
4 2
4 6
Вихідні дані
Case #1: 1
Case #2: 1
Case #3: 0
Case #4: 3
Case #5: 9