eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
5
2 0
2 2
4 1
4 2
4 6
Вихідні дані #1
Case #1: 1
Case #2: 1
Case #3: 0
Case #4: 3
Case #5: 9