$\because C_{p}^{i}=\frac{p!}{i!(p-i)!} = \frac{p}{i}\frac{(p-1)!}{(i-1)!(p-1-(i-1))!} = \frac{p}{i}C_{i-1}^{p-1}$
$\therefore C_{p}^{i}\equiv \frac{p}{i}C_{p-1}^{i-1}\equiv 0\ (mod\ p)\ (1\leq i\leq p-1)$
$\therefore (1+x)^p\equiv C_{p}^{0}x^01^p+C_{p}^{1}x^11^{p-1}+C_{p}^{2}x^21^{p-2}+\cdot \cdot \cdot \ +C_{p}^{p}x^p1^0\equiv 1+x^p\ (mod\ p)$
令 $n=sp+q,m=lp+r\ (0\leq q,r\leq p-1)$
$\because n=sp+q$
$\therefore (1+x)^{n}=(1+x)^{sp}(1+x)^{q}$
$\because (1+x)^{p}\equiv 1+x^p\ (mod\ p)$
$\therefore (1+x)^{sp}\equiv ((1+x)^p)^s\equiv (1+x^p)^s\ (mod\ p)$
$\therefore (1+x)^n\equiv (1+x^p)^s(1+x)^q\ (mod\ p)$
$\therefore C_{n}^{m}x^m1^{n-m}\equiv C_{s}^{l}(x^p)^l1^{s-l}\cdot C_{q}^{r}x^r1^{q-r}\ (mod\ p)$
$\therefore C_{n}^{m}x^m\equiv C_{s}^{l}\cdot C_{q}^{r}x^{lp+r}\equiv C_{s}^{l}\cdot C_{q}^{r}x^m\ (mod\ p)$
$\therefore C_{n}^{m}x^m\equiv C_{s}^{l}\cdot C_{q}^{r}\equiv C_{[\frac{n}{p}]}^{[\frac{m}{p}]}\cdot C_{n\ mod\ p}^{m\ mod\ p}\ (mod\ p)$
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e5+5; 5 ll a[maxn]; 6 ll qmul(ll a, ll b, ll p) { 7 ll ans = 0; 8 while (b) { 9 if (b&1) ans = (ans+a)%p; 10 a = (a+a)%p; 11 b >>= 1; 12 } 13 return ans%p; 14 } 15 ll qpow(ll a, ll b, ll p) { 16 ll ans = 1; 17 while (b) { 18 if (b&1) ans = qmul(ans,a,p); 19 a = qmul(a,a,p); 20 b >>= 1; 21 } 22 return ans%p; 23 } 24 ll comb(ll n, ll m, ll p) { 25 if (m > n) return 0; 26 return ((a[n]*qpow(a[m],p-2,p))%p * qpow(a[n-m],p-2,p)%p)%p; 27 } 28 ll lucas(ll n, ll m, ll p) { 29 if (m == 0) return 1; 30 return comb(n%p,m%p,p)*lucas(n/p,m/p,p)%p; 31 } 32 void init(ll p) { 33 a[0] = 1; 34 for (int i = 1; i <= p; i++) { 35 a[i] = a[i-1]*i%p; 36 } 37 } 38 int main() { 39 int t; scanf("%d",&t); 40 while (t--) { 41 ll n, m, p; scanf("%lld%lld%lld",&n,&m,&p); 42 init(p); 43 printf("%lld\n",lucas(n+m,m,p)); 44 } 45 return 0; 46 }