Description

给定$n$组询问，每组询问给定两个整数$a$，$b$，$p$，其中$p$是质数，请你输出 $C^b_a mod p$的值。

Input Format

第一行包含整数 $n$。
接下来 $n$行，每行包含一组$a$和$b$,$p$。

Output Format

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

3
5 3 7
3 1 5
6 4 13

3
3
2

Hint

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

Source

2.4数学知识 求组合数