Masz $q$ zapytań. Dla każdego zapytania musisz obliczyć liczbę dzielników symbolu Newtona $\binom{n}{m}$.

Ponieważ wynik może być bardzo duży, należy wypisać go modulo $p = 10^9 + 7$.

Wejście

W pierwszej linii znajduje się jedna liczba całkowita dodatnia $q$, oznaczająca liczbę zapytań.

Następnie w $q$ liniach znajdują się po dwie liczby całkowite $n, m$, przy czym $0 \le m \le n$.

Wyjście

Wypisz $q$ linii, z których każda zawiera wynik dla odpowiedniego zapytania.

Podzadania

Dla $10\%$ danych wejściowych zachodzi $q \le 10^{3}, n \le 10^{3}$.

Dla $50\%$ danych wejściowych zachodzi $q \le 10^{5}, n \le 10^{5}$.

Dla $100\%$ danych wejściowych zachodzi $q \le 5\times 10^{5}, n \le 10^{6}$.

Przykład

Wejście 1

4
0 0
1 0
2 1
3 2

Wyjście 1

1
1
2
2

Wejście 2

5
3 2
5 3
5 4
6 2
8 3

Wyjście 2

2
4
2
4
8