该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

zj 正在做关于组合数的数学题，每次做都对，但题目太多了，他想偷懒，然而他又不会编程，想找你帮忙解决。给定 $t$ 组询问，每组询问给定三个整数 $a,b,p$, 其中 $p$ 是质数，请你输出 $C_a^b \mod p$ 的值。

输入格式

第一行包含整数 $t$ ($1 \le t \le 20$)，表示询问次数。

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

其中，$1\le b\le a\le 10^{18}, 1\le p \le 10^5。$

输出格式

输出 $n$ 行，每行对应相应参数的解。

输入样例

3
5 3 7
3 1 5
6 4 13

输出样例

3
3
2