卢卡斯定理

//卢卡斯定理 可求在模p意义下的组合数 
//公式：C(x,y)=C(x/p,y/p)*C(x%p,y%p) (mod p) 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
ll T,n,m,p,a[100001];
using namespace std;
ll qpow(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%p;
        x=x*x%p;
        y/=2;
    }
    return ans;
}
ll c(ll x,ll y)
{
    if(x<y) return 0;
    return a[x]*qpow(a[y],p-2)%p*qpow(a[x-y],p-2)%p;
}
ll lucas(ll x,ll y)
{
    if(!y) return 1;
    return lucas(x/p,y/p)*c(x%p,y%p)%p;
}
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&m,&p);
        a[0]=1;
        for(ll i=1;i<=p;i++)
            a[i]=a[i-1]*i%p;
        printf("%lld
",lucas(n+m,m));
    }
    return 0;
}