Розташування

У класі є $m$ учнів, серед яких $n$ дівчат. Учитель, містер X, хоче вишикувати всіх учнів у рядок. Оскільки він вважає, що дівчата з його класу дуже балакучі, він не хоче, щоб дві дівчини стояли поруч. Містер X хоче дізнатися, скількома способами він може вишикувати всіх $m$ учнів у рядок, дотримуючись цієї умови. Допоможіть йому знайти кількість таких способів.

Вхідні дані

Перша стрічка містить кількість тестів $t(1\le t\le 10^5)$. Кожен з наступних $t$ рядків містить два цілі числа $m$ і $n(1<n\le m\le 10^6)$.

Вихідні дані

Для кожного тесту виведіть відповідь за модулем $10^9+7$ в окремому рядку.

Приклади