FZU 2020 Comb(拡張ユークリッド求逆元)

/*
      ；

C(n,m)= n*(n-1)*...*(n-m+1) / m!;
     ，m   10^4，1s   (     10^7)，         ；

  ： fz:     ：fz= n*(n-1)*...*(n-m+1);  10^4   ，
      ；

  ： fm:     ：fm= m*(m-1)*...*2*1;  10^4   ，
      ；

         p         ；
*/

#include <cstdio>
#include <iostream>
using namespace std;

int ext_gcd(int a, int b, int &x, int &y){
    if( !b ) return x=1,y=0,a;
    int d= ext_gcd(b, a%b, y, x);
    y-= a/b*x;
    return d;
}
int Inv(int a, int m){
    int d,x,y;
    d= ext_gcd(a,m,x,y);
    return (x%m+m)%m;
}

/*     C(n,m)%p，  m<=10^4,p   ， m<p;
fm:     ：fm= m*(m-1)*...*2*1;
fz:     ：fz= n*(n-1)*...*(n-m+1);

           ，
      （   ）   p   ，     ；
C(n,m)= n*(n-1)*...*(n-m+1) / m!;
C(n,m)%p = (fz%p) * Inv( (fm%p), p ) %p;

*/
long long Comb(int n, int m, int p){
    long long fm=1, fz= 1;
    for(int i=2; i<=m; ++i)
        fm= fm*i%p;
    for(int i=n-m+1; i<=n; ++i)
        fz= fz*i%p;
    long long ret= fz * Inv( fm, p ) %p;
    return ret<0 ? ret+p : ret;
}

int main()
{
    //freopen("E.in","r",stdin);
    int T,n,m,p;
    cin>>T;
    while( T-- ){
        cin>>n>>m>>p;
        cout<< Comb( n, m, p ) <<endl;
    }
}