组合数模板

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10,mod=1e9+7;
typedef long long ll;
struct CalC {
    
    ll f[N], inff[N];
    ll imp(ll a, ll k, ll q) {
    
        ll res = 1;
        while (k) {
    
            if (k & 1) res = res * a % q;
            a = a * a % q;
            k >>= 1;
        }
        return res;
    }
    void init() {
    
        f[0] = inff[0] = 1;
        for (int i = 1; i < N; i++) {
    
            f[i] = f[i - 1] * i % mod;
            inff[i] = inff[i - 1] * imp(i, mod - 2, mod) % mod;
        }
    }
    ll C(ll a, ll b) {
    
        if (a == b)return 1;
        if (a < b)return 0;
        return f[a] * inff[b] % mod * inff[a - b] % mod;
    }
    int lucas_C(ll a, ll b, ll p)/
    {
    
        if (a < b) return 0;

        int down = 1, up = 1;
        for (int i = a, j = 1; j <= b; i--, j++)
        {
    
            up = up * i % p;
            down = down * j % p;
        }

        return up * imp(down, p - 2, p) % p;//其实优化之处就是把原本每次for循环都要qmi求的逆元优化到最后一步返回值的时候来求解
    }

    int lucas(ll a, ll b, ll p)///O(plogn)p为取模质数
    {
    
        if (a < p && b < p) return lucas_C(a, b, p);//这一步从定义出发计算即可
        return lucas_C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
        //a%p后肯定是<p的,所以可以用C(),但a/p后不一定<p 所以用lucas继续递归
    }

}Cal;
int main() {
    
    Cal.init();
    int n; cin >> n;
    while (n--)
    {
    
        ll a, b, p; cin >> a >> b >> p;
        cout << Cal.lucas(a, b, p) << endl;
    }
}