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

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

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

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

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

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

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

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

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

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