题目描述
给出组合数
C(n,m)
C(n,m) 表示从
n
n 个元素中选出
m
m 个元素的方案数。例如
C(5,2) = 10, C(4,2) = 6
C(5,2)=10,C(4,2)=6。可是当
n,m
n,m 比较大的时候，
C(n,m)
C(n,m) 很大。于是 xiaobo 希望你输出
C(n,m) \bmod p
C(n,m)modp 的值。
输入
输入数据第一行是一个正整数
T
T，表示数据组数；
接下来是
T
T 组数据，每组数据有
3
3 个正整数
n,m,p
n,m,p。
输出
对于每组数据，输出一个正整数，表示
C(n,m) \bmod p
C(n,m)modp 的结果。
样例输入
2
5 2 3
5 2 61
样例输出
1
10
提示
数据范围与提示
对于所有数据，
T\le 100
T≤100，
1\le m\le n\le 10^9
1≤m≤n≤109，
m\le 10^4
m≤104，
m\lt p\lt 10^9
m
p
p 是素数。来源/分类
ybttg 组合计数 lucas定理