5358 - 组合数学:求组合数(模版1)

通过次数

42

提交次数

94

时间限制 : 1 秒
内存限制 : 128 MB

给定n组询问,每组询问给定的2个整数a,b, 请你输出C_a^b mod (10^9+7)的值

输入

第一行包含整数n 接下来n行,每行包含一组a和b

输出

共n行,每行输出一个询问的解

样例

输入

3
3 1
5 3
2 2

输出

3
10
1

提示

数据范围

1<=n<=10000
1<=b<=a<=2000