HDU - 3037：Saving Beans

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<vector>

#define MAXN 100000+10

#define ll long long

#define pb push_back

#define ft first

#define sc second

#define mp make_pair

#define pil pair<int,ll>

using namespace std;

int n,m,p;

ll fac[MAXN],inv[MAXN],finv[MAXN];

ll Pow(ll x,ll p,ll MOD){

    ll ret=;

    while(p){

        if(p&){(ret*=x)%=MOD;}

        (x*=x)%=MOD;

        p>>=;

    }

    return ret;

}

ll ni(ll x){

    return Pow(x,p-,p);

}

ll C(int n,int m){

    if(m>n)return ;

    return fac[n]*ni(fac[m])*ni(fac[n-m])%p;

}

ll lucas(int n,int m){

    ll ret=;

    while(n>=p||m>=p){

        if(!m)return ret;

        int t1=n%p,t2=m%p;

        if(t1<t2)return ;

        (ret*=C(t1,t2))%=p;

        n/=p,m/=p;

    }

    return ret*C(n,m)%p;

}

void solve(){

    scanf("%d%d%d",&n,&m,&p);

    fac[]=fac[]=;

//    finv[0]=finv[1]=1;

//    inv[1]=1;

    for(int i=;i<=p;i++){

        fac[i]=fac[i-]*i%p;

//        inv[i]=p-(inv[p%i]*(p/i)%p);

//        finv[i]=finv[i-1]*inv[i]%p;

    }

    printf("%lld\n",lucas(n+m,m));

}

int main()

{

//    freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--){

        solve();

    }

    return ;

}