void solve_lucas() {
    // Chỉ hoạt động nếu m là số nguyên tố
    // Công thức: C(n, k) mod m = product of C(n_i, k_i) mod m
    // Trong đó n_i, k_i là các chữ số trong cơ sở m
    if (is_prime(m)) {
        ll res = 1;
        while (n > 0 || k > 0) {
            ll ni = n % m;
            ll ki = k % m;
            if (ki > ni) { cout << 0; return; }
            res = (res * C_mod_prime(ni, ki, m)) % m;
            n /= m;
            k /= m;
        }
        cout << res;
    }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// Phân tích m thành thừa số nguyên tố
vector<pair<ll, int>> prime_factors(ll m) {
    vector<pair<ll, int>> factors;
    for (ll i = 2; i * i <= m; ++i) {
        if (m % i == 0) {
            int cnt = 0;
            while (m % i == 0) {
                m /= i;
                cnt++;
            }
            factors.push_back({i, cnt});
        }
    }
    if (m > 1) factors.push_back({m, 1});
    return factors;
}

// Tính số mũ của p trong n! (Legendre's formula)
ll get_power(ll n, ll p) {
    ll res = 0;
    while (n) {
        res += n / p;
        n /= p;
    }
    return res;
}

// Tính n! / p^a mod p^b (loại bỏ hết thừa số p)
ll factorial_mod_prime_power(ll n, ll p, ll pe) {
    if (n == 0) return 1;
    ll res = 1;
    // Tính tích các số không chia hết cho p
    for (ll i = 1; i < pe; ++i) {
        if (i % p != 0) res = (__int128)res * i % pe;
    }
    res = pow_mod(res, n / pe, pe); // Lặp lại pe! ^ (n/pe)
    // Xử lý phần còn lại
    for (ll i = 1; i <= n % pe; ++i) {
        if (i % p != 0) res = (__int128)res * i % pe;
    }
    return (__int128)res * factorial_mod_prime_power(n / p, p, pe) % pe;
}

// Hàm tính C(n, k) mod m
ll solve(ll n, ll k, ll m) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1 % m;
    auto factors = prime_factors(m);
    vector<ll> remainders;
    for (auto [p, a] : factors) {
        ll pe = 1;
        for (int i = 0; i < a; ++i) pe *= p;

        ll exponent = get_power(n, p) - get_power(k, p) - get_power(n - k, p);
        if (exponent >= a) {
            remainders.push_back(0);
            continue;
        }

        ll num = factorial_mod_prime_power(n, p, pe);
        ll den_k = factorial_mod_prime_power(k, p, pe);
        ll den_nk = factorial_mod_prime_power(n - k, p, pe);
        ll den = (__int128)den_k * den_nk % pe;

        ll inv_den = 1;
        // Tính nghịch đảo modular, den va pe co gcd = 1
        // Su dung Extended Euclid hay Fermat de tinh inv
        // O day su dung Extended Euclid
        ll x, y;
        extgcd(den, pe, x, y);
        inv_den = (x % pe + pe) % pe;

        ll val = (__int128)num * inv_den % pe;
        val = (__int128)val * pow_mod(p, exponent, pe) % pe;
        remainders.push_back(val);
    }

    // Dung CRT de ket hop cac ket qua
    ll res = 0, mod = 1;
    for (int i = 0; i < factors.size(); ++i) {
        ll pe = 1;
        for (int j = 0; j < factors[i].second; ++j) pe *= factors[i].first;
        // Cong thuc CRT
        // ... (code CRT)
    }
    return res;
}

// Cach 1: Neu m nho, co the tinh binh thuong
// Cach 2: Su dung cong thuc C(n, k) = (n-k+1)/1 * (n-k+2)/2 * ... * n/k
// Voi m nguyen to, ta co the chia binh thuong.
// Voi m khong nguyen to, phai su dung Extended Euclid cho tung buoc.

ll solve_optimized(ll n, ll k, ll m) {
    if (k > n - k) k = n - k;
    ll res = 1;
    for (ll i = 1; i <= k; ++i) {
        ll mul = n - k + i;
        // Cong thuc: res = res * mul / i
        // res = (res * mul) / i
        // De lay modulo, ta can tinh res * mul * inv(i) mod m
        // Tuy nhien, inv(i) chi ton tai neu gcd(i, m) = 1.
        // Neu m co n phan tu, i co the chia het m.
        // 
        // Cach khac: Giai pt tuyen tinh: res * mul = ans * i (mod m)
        // Hay su dung thuat toan fragmentary remainder sequence
    }
    return res % m;
}