5359 - 组合数学：求组合数（模版3）
Time Limit : 1 秒
Memory Limit : 128 MB
给定n组询问，每组询问给定的2个整数a,b, 请你输出C_a^b mod p的值 ,p为素数
Input
第一行包含整数 n 。 接下来 n 行，每行包含一组 a , b , p
Output
共 n 行，每行输出一个询问的解。
Examples
Input
1 2 1 10007
Output
2
Hint
数据范围 1 ≤ n ≤ 20 , 1 ≤ b ≤ a ≤ 1 × 1 0^18 , 1 ≤ p ≤ 1 0^5