5359 - 组合数学:求组合数(模版3)

给定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

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题