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

using i64 = long long;

int mod;

int qpow(int a, int b) {
    int res = 1;
    for (; b; b /= 2, a = 1ll * a * a % mod) {
        if (b & 1) {
            res = 1ll * res * a % mod;
        }
    }
    return res;
}

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

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