using ll = long long;
ll quick_pow(ll a, ll b, ll m) {
    ll ans = 1 % m;
    ll w = a;
    while (b) {
        if (b % 2 == 1) ans = ans * w % m;
        w = w * w % m;
        b /= 2;
    }
    return ans;
}

// 位运算版
ll qpow(ll a, ll b, ll p) {
    ll ans = 1 % p;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}