有两个点，第一个是$lucas$定理的公式，另外一个是求$C_{a}^{b}$的函数

1. $Lucas$定理：$C_{a}^{b} \equiv C_{a \% p}^{b \% p} * C_{\frac{a}{p}}^{\frac{b}{p}}(mod p)$
2. 为什么可以这样求解$C_{a}^{b}$:
   $C_{a}^{b} = \frac{a!}{(a - b)! * b!} = \frac{a * (a - 1) * (a - 2) * … * (a - b + 1) * (a - b) * … * 1}{(a - b) * (a - b - 1) * … * 1 * b!} = \frac{a * (a - 1) * (a - 2) * … (a - b + 1)}{b!}$
   因此就可以递推的每次乘$a$然后除以$b$, 因为从$a$到$a - b + 1$, 所以就是乘$b$次

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 6;

ll poww(ll a, ll b, ll p){
    ll res = 1 % p;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

ll C(ll a, ll b, ll p){
    ll res = 1;
    for(int i = 1, j = a;i <= b;++i, --j){
        res = res * j % p;
        res = res * poww(i, p - 2, p) % p;
    }
    return res % p;
}

ll lucas(ll a, ll b, ll p){
    if(a < p && b < p) return C(a, b, p);
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

int main(){
    int n; sd(n);
    while(--n >= 0){
        ll a, b; sld(a), sld(b);
        ll p; sld(p);
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}