题目描述

你有 $q$ 组询问，每组询问你需要计算出组合数 $\binom{n}{m}$ 的因子数量。

由于答案可能很大，你只需要输出将答案对 $p = 10^9 + 7$ 取模的结果即可。

输入格式

第一行一个正整数 $q$ 表示询问数量。

接下来 $q$ 行，每行两个整数 $n, m$，保证 $0\le m \le n$。

输出格式

输出 $q$ 行，每行一个整数对应该询问的答案。

样例数据

样例 1 输入

4
0 0
1 0
2 1
3 2

样例 1 输出

1
1
2
2

样例 2 输入

5
3 2
5 3
5 4
6 2
8 3

样例 2 输出

2
4
2
4
8

子任务

对于 $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}$。