1450. 组合数

给定 nn 组询问,每组询问给定整数 a,ba,b,计算 Cba(mod109+7)C^a_b \pmod {10^9+7} 的值。

输入

多组询问,第一行一个整数 nn

接下来 nn 行,每行两个整数 a,ba,b

子任务分值测试点数量nna,ba,b
11707015151n1041 \leq n \leq 10^41ba20001 \leq b \leq a \leq 2000
223030551n1051 \leq n \leq 10^51ba1051 \leq b \leq a \leq 10^5

输出

输出 nn 行,每行输出一个询问的解。

样例

标准输入 复制文本
3
3 1
5 3
2 2
标准输出 复制文本
3
10
1
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 128
通过 44