Masz $q$ zapytań, w każdym z nich musisz obliczyć liczbę dzielników symbolu Newtona $\binom{n}{m}$.
$\binom{n}{m}$ oznacza liczbę sposobów wyboru $m$ elementów z $n$ różnych elementów, czyli:
$$ \binom{n}{m} = \frac{n!}{m!(n-m)!} $$
Ponieważ wynik może być bardzo duży, należy wypisać wynik modulo $p = 10^9 + 7$.
Wejście
Dane wczytywane ze standardowego wejścia.
Pierwsza linia zawiera jedną liczbę całkowitą dodatnią $q$ oznaczającą liczbę zapytań.
Następnie $q$ linii, każda zawiera dwie liczby całkowite $n, m$, przy czym $0\le m \le n$.
Wyjście
Wypisz na standardowe wyjście $q$ linii, każda zawierająca jedną liczbę całkowitą będącą odpowiedzią na dane zapytanie.
Przykład
Wejście 1
3 0 0 4 2 10 3
Wyjście 1
1 4 16
Uwagi
$\binom 0 0 = 1$, ma $1$ dzielnik.
$\binom 4 2 = 6$, ma $4$ dzielniki: $\{1, 2, 3, 6\}$.
$\binom {10} 3 = 120$, ma $16$ dzielników: $\{1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120\}$.
Przykład 2
Zobacz pliki ex_divisor2.in oraz ex_divisor2.ans w katalogu z plikami do pobrania.
Podzadania
Dla $100\%$ danych wejściowych zachodzi $q \le 10^{5}, n \le 10^{5}$.
| Test | $n$ | $q$ | Własności specjalne |
|---|---|---|---|
| $1$ | $\le 20$ | $=10^2$ | brak |
| $2$ | $=10^5$ | ||
| $3,4$ | $\le 3,000$ | $=3,000$ | |
| $5$ | $\le 10^5$ | A | |
| $6$ | $=10^5$ | ||
| $7,8$ | B | ||
| $9,10$ | brak |
Własność specjalna A: gwarantuje, że $\binom n m \le 10^6$.
Własność specjalna B: gwarantuje, że wartość $n$ w każdym zapytaniu jest taka sama.