using i64 = long long;

i64 mod;

i64 qpow(i64 a, i64 b) {
    i64 res = 1;
    while(b) {
        if(b&1) res = (res * a) % mod;
        a = (a*a) %mod;
        b >>= 1;
    }

    return res;
}

void init(int p) {
    mod = p;
}

i64 inv(int a) {
    return qpow(a, mod-2);
}