4200 : 组合数学进阶-Lucas 定理

Coding is the closest thing we have to superpower ！

描述

Lucas定理可以表示为： $C_n^m \bmod p = C_{n/p}^{m/p} * C_{n \% p}^{m \% p} \bmod p$

给定整数 $n, m, p$ 的值，求出 $C_{n + m}^n \bmod p$ 的值。
输入数据保证 $p$ 为质数。

输入

第一行一个整数 $T$ ，表示数据组数。
对于每组数据，输入一行三个整数 $n, m, p$ 。

对于 $100\%$ 的数据， $1 \leq n, m, p \leq 10^5$ ， $1 \leq T \leq 10$ 。

输出

对于每组数据，输出一行，一个整数，表示所求的值。

样例

2
1 2 5
2 1 5

3
3

标签

组合数学 Lucas 定理