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

$\binom{n}{m}$ обозначает количество способов выбрать $m$ объектов из $n$ различных объектов, то есть

$$ \binom{n}{m} = \frac{n!}{m!(n-m)!} $$

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

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

Данные считываются из стандартного ввода.

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

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

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

Вывод осуществляется в стандартный вывод.

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

Примеры

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

3
0 0
4 2
10 3

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

1
4
16

Примечание

$\binom 0 0 = 1$, имеет $1$ делитель.

$\binom 4 2 = 6$, имеет $4$ делителя: $\{1, 2, 3, 6\}$.

$\binom {10} 3 = 120$, имеет $16$ делителей: $\{1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120\}$.

Пример 2

Смотрите файлы ex_divisor2.in и ex_divisor2.ans в скачиваемом архиве.

Подзадачи

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

Особое свойство A: гарантируется, что $\binom n m \le 10^6$.

Особое свойство B: гарантируется, что значение $n$ во всех запросах одинаково.