887. 求组合数 III

给定$n$组询问,每组询问给定三个整数$a, b, p$,其中$p$是质数,请你输出$C_a^b\ mod\ p$的值。

输入格式

第一行包含整数$n$。

接下来$n$行,每行包含一组$a, b, p$。

输出格式

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

数据范围

$1 \le n \le 20$,
$1 \le b \le a \le 10^{18}$,
$1 \le p \le 10^5$,

输入样例:

3
5 3 7
3 1 5
6 4 13

输出样例:

3
3
2