e-olymp
Yarışlar

2018 Petrozavodsk, Winter, Jagiellonian University

Секретный Санта

Каждое Рождество члены сообщества энтузиастов алгоритмов посылают друг другу подарки. Эта традиция немного проблематична и приводит к конфликтам, потому что некоторые участники всегда получают больше подарков, чем другие. В этом году сообщество решило ввести скоординированную и справедливую систему, известную как Секретный Санта.

Идея создания Секретный Санта очень проста: каждому члену сообщества назначается человек, которому он отправляют подарок. Таким образом, каждый участник готовит один подарок и получает один подарок. Возможно, что некоторые участники назначают сами себя, тогда они просто отправляют подарок себе.

Сообщество с энтузиазмом относится к этой идее, и теперь оно хочет определить, кто кому отправит подарок. Тем не менее, необходимо помнить, как работает почтовая система - возможность доставки посылки из одного города в другой зависит от силы ветра в этот день.

Имеется n членов сообщества. Каждый участник живет в отдельном городе, города пронумерованы от 1 до n. Если скорость ветра равна a, то посылка с подарком может быть отправлена из города k в город l тогда и только тогда, когда k - n + a < l < k + a.

Ваша задача - найти количество способов назначить членов сообщества, чтобы все могли отправлять свои подарки в один и тот же день, учитывая скорость ветра в этот день. Поскольку число может быть очень большим, Вам нужно только найти значение по модулю 109 + 7.

Входные данные

Первая строка содержит количество тестов z (1z10). Далее следуют описания тестов.

Каждый тест расположен в отдельной строке и содержит два целых числа n и a (1a200, 1n106, a < n) - соответственно количество членов сообщества и сила ветра.

Выходные данные

Для каждого теста выведите одно целое число: количество способов, которыми члены сообщества могут быть назначены друг другу, вычисленное по модулю 109 + 7.

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
4 2
5 2
16 5
Çıxış verilənləri #1
5
13
418144253
Mənbə 2018 Петрозаводск, Зима, Jagiellonian U, Январь 30, Задача D