给定 $T$ 组询问，每组询问给定两个整数 $a, b$，请你输出 $C_a^b \; mod \; (10^9 + 7)$ 的值。

输入格式

第一行输入一个正整数 $T$ $(1 \leq T \leq 10^5)$

接下来 $T$ 行，每行输入两个正整数 $a, b$ $(1 \leq b \leq a \leq 5000)$

输出格式

输出 $T$行，每行一个整数为询问的解

样例 1

输入：

3
3 1
5 3
2 2

输出：

3
10
1

来源：Luogu_T465471。本站使用重新构建的测试数据。