给定 nnn 组询问,每组询问给定整数 a,ba,ba,b,计算 Cba(mod109+7)C^a_b \pmod {10^9+7}Cba(mod109+7) 的值。
输入
多组询问,第一行一个整数 nnn。
接下来 nnn 行,每行两个整数 a,ba,ba,b。
输出
输出 nnn 行,每行输出一个询问的解。
样例
3 3 1 5 3 2 2
3 10 1