Перестановки с данной дистанцией
У Батхеда есть n томов его любимой Энциклопедии Для Глупых Подростков. Тома пронумерованы от 1 до n и выстроены в ряд. Он не любит строгого порядка, но также он не любит и полнейшего хаоса. Батхед рассчитывает дистанцию перестановки томов как сумму разностей номера и позиции для всех томов. Другими словами, если перестановка имеет вид (i[1], i[2], ... i[n]), где i[k] (1 ≤ k ≤ n) означает номер тома на k-м месте, то её дистанция равна |i[1] – 1| + |i[2] – 2| + ... + |i[n] – n|. Любимое число Батхеда равно d, и он хочет выстроить тома Энциклопедии так, чтобы дистанция была равна d. Сколькими способами он может это сделать?
Входные данные
Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 100). Каждая из следующих T строк содержит данные для одного теста: количество томов n (1 ≤ n ≤ 50) и требуемую дистанцию d (0 ≤ d ≤ 10000), которые разделены пробелом. Числа n, d – целые.
Выходные данные
Выведите T строк вида Case #A: B, где A – номер теста (начиная с 1), B – количество перестановок n томов с дистанцией d, взятое по модулю 100007.