5359 - 组合数学：求组合数（模版3）
时间限制 : 1 秒
内存限制 : 128 MB
给定n组询问，每组询问给定的2个整数a,b, 请你输出C_a^b mod p的值 ,p为素数
输入
第一行包含整数 n 。 接下来 n 行，每行包含一组 a , b , p
输出
共 n 行，每行输出一个询问的解。
样例
输入
1 2 1 10007
输出
2
提示
数据范围 1 ≤ n ≤ 20 , 1 ≤ b ≤ a ≤ 1 × 1 0^18 , 1 ≤ p ≤ 1 0^5