$q$ 個のクエリが与えられます。各クエリについて、二項係数 $\binom{n}{m}$ の約数の個数を計算してください。
$\binom{n}{m}$ は $n$ 個の異なるボールから $m$ 個のボールを選ぶ組み合わせの数であり、以下のように定義されます。
$$ \binom{n}{m} = \frac{n!}{m!(n-m)!} $$
答えは非常に大きくなる可能性があるため、答えを $p = 10^9 + 7$ で割った余りを出力してください。
入力
標準入力からデータを読み込みます。
1 行目にクエリの数 $q$ が与えられます。
続く $q$ 行には、それぞれ 2 つの整数 $n, m$ が与えられます。ただし、$0 \le m \le n$ を満たします。
出力
標準出力へ出力します。
$q$ 行にわたり、各クエリに対する答えを 1 行ずつ出力してください。
入出力例
入力 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 を参照してください。
出力 2
ダウンロードディレクトリ内の ex_divisor2.ans を参照してください。
サブタスク
すべてのデータにおいて、$q \le 10^{5}, n \le 10^{5}$ を満たします。
| テストケース | $n$ | $q$ | 特殊性質 |
|---|---|---|---|
| $1$ | $\le 20$ | $=10^2$ | なし |
| $2$ | $=10^5$ | ||
| $3,4$ | $\le 3,000$ | $=3,000$ | |
| $5$ | $\le 10^5$ | A | |
| $6$ | $=10^5$ | ||
| $7,8$ | B | ||
| $9,10$ | なし |
特殊性質 A：$\binom n m \le 10^6$ であることが保証される。
特殊性質 B：入力される $n$ の値が常に同一であることが保証される。