e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
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