传送门：
P3807 【模板】卢卡斯定理/Lucas 定理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/problem/P3807题干：
给定整数n,m,p 的值，求出C（n+m，n）mod p 的值。
输入数据保证 p 为质数。
注: C 表示组合数。
输入格式
本题有多组数据。
第一行一个整数 T，表示数据组数。
对于每组数据:
一行，三个整数 n,m,p。
输出格式
对于每组数据，输出一行，一个整数，表示所求的值。
输入输出样例
输入 #1复制
2 1 2 5 2 1 5输出 #1复制
3 3说明/提示
对于 100% 的数据1≤n,m,p≤10^5，1≤T≤10。
Lucas 定理：
相当于：
这是一道板子题，由组合数的公式：
我们不难发现 只要求出 递推n！模上p的值，就能得到 m！，（n-m）！。
然后因为m！，（n-m）！在分母，所以我们只需要求出 逆元即可。
由于模数p是质数，所以用到费马小定理求解。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;typedef long long ll;
const ll N = 1e5+7;
const ll M = 1e6+7;
ll fac[N],C[N];
ll get_inv(ll a,ll b,ll p) {ll s = 1;while (b) {if (b & 1)s = s * a % p;a = a * a % p;b >>= 1;}return s;
}
ll get_C(ll n, ll m,ll P) {if (m > n)return 0;return (fac[n] * get_inv(fac[m],P-2,P) % P) * get_inv(fac[n - m],P-2,P) % P;
}
ll Lucas(ll n,ll m,ll P) {if (m == 0)return 1;return get_C(n % P, m % P,P) * Lucas(n / P, m / P,P)%P;
}int main() {int t;cin >> t;while (t--) {ll n, m,p;cin >> n >> m >> p;fac[0] = 1;for (ll i = 1; i <= n+m; i++) {fac[i] = fac[i - 1] * i % p;}cout << Lucas(n+m, n, p)<<endl;}
}
