Секретний Санта
Кожного Різдва члени спільноти ентузіастів алгоритмів обмінюються подарунками. Ця традиція іноді викликає конфлікти, адже деякі учасники отримують більше подарунків, ніж інші. Цього року спільнота вирішила запровадити скоординовану та справедливу систему, відому як Таємний Санта.
Ідея Таємного Санти проста: кожному члену спільноти призначається людина, якій він надсилає подарунок. Таким чином, кожен учасник готує один подарунок і отримує один подарунок. Можливо, що деякі учасники призначають самі себе, і в такому випадку вони просто надсилають подарунок собі.
Спільнота з ентузіазмом підтримала цю ідею, і тепер вона хоче визначити, хто кому надішле подарунок. Проте, необхідно враховувати, як працює поштова система - можливість доставки посилки з одного міста в інше залежить від сили вітру в цей день.
Є n членів спільноти. Кожен учасник живе в окремому місті, міста пронумеровані від 1 до n. Якщо швидкість вітру дорівнює a, то посилка з подарунком може бути відправлена з міста k в місто l тоді і тільки тоді, коли k - n + a < l < k + a.
Ваше завдання - знайти кількість способів призначити членів спільноти так, щоб усі могли надсилати свої подарунки в один і той же день, враховуючи швидкість вітру в цей день. Оскільки число може бути дуже великим, вам потрібно знайти значення за модулем 10^9 + 7.
Вхідні дані
Перший рядок містить кількість тестів z (1 ≤ z ≤ 10). Далі слідують описи тестів.
Кожен тест розташований в окремому рядку і містить два цілих числа n і a (1 ≤ a ≤ 200, 1 ≤ n ≤ 10^6, a < n) - відповідно кількість членів спільноти і сила вітру.
Вихідні дані
Для кожного тесту виведіть одне ціле число: кількість способів, якими члени спільноти можуть бути призначені один одному, обчислене за модулем 10^9 + 7.