D. Сочетания по модулю

Теперь ответы большие, и их просят по модулю $10^9 + 7$.

Дано $q$ запросов; в каждом надо вывести $\binom{n}{k} \bmod (10^9+7)$.

Отвечать на каждый запрос отдельно не выйдет — запросов слишком много. Подготовьте факториалы и обратные к ним один раз, и каждый ответ станет двумя умножениями.

Первая строка содержит число $q$ ($1 \le q \le 2 \cdot 10^5$).

Далее идут $q$ строк, в каждой числа $n$ и $k$ ($0 \le k \le n \le 2 \cdot 10^5$).

Для каждого запроса выведите ответ на отдельной строке.