В классе m учеников, из них n девочек. Учитель, мистер X, хочет выстроить всех учеников в ряд. X считает, что девочки из его класса очень разговорчивы. Поэтому он не хочет, чтобы две девочки располагались рядом. Мистер X хочет знать, сколькими способами он сможет выстроить в ряд всех m учеников. Помогите ему.
Первая строка содержит количество тестов t (1≤t≤105). Каждая из следующих t строк содержит два целых числа m и n (1<n≤m≤106).
Для каждого теста выведите ответ по модулю 109+7 в одной строке.