У вас есть $q$ запросов, для каждого из которых необходимо вычислить количество делителей биномиального коэффициента $\binom{n}{m}$.

Так как ответ может быть очень большим, выведите результат по модулю $p = 10^9 + 7$.

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

В первой строке задано целое положительное число $q$ — количество запросов.

Далее следуют $q$ строк, каждая из которых содержит два целых числа $n$ и $m$, при этом гарантируется, что $0\le m \le n$.

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

Выведите $q$ строк, в каждой из которых должно быть целое число — ответ на соответствующий запрос.

Подзадачи

Для $10\%$ данных гарантируется, что $q \le 10^{3}, n \le 10^{3}$.

Для $50\%$ данных гарантируется, что $q \le 10^{5}, n \le 10^{5}$.

Для $100\%$ данных гарантируется, что $q \le 5\times 10^{5}, n \le 10^{6}$.

Примеры

Пример 1

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

4
0 0
1 0
2 1
3 2

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

1
1
2
2

Пример 2

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

5
3 2
5 3
5 4
6 2
8 3

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

2
4
2
4
8