#include "inv.h"
#include <vector>
#include <iostream>
const int N = 1e7 + 10;
std::vector<int> vec(N);
int quickPow(int base, int power, int mod) {
    int result = 1;
    base = base % mod;
    while (power > 0) {
        if (power & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        power >>= 1;
    }
    return result;
}
void init(int p) {
    vec[1] = 1;
    for (int i = 2; i < N; i++) {
        vec[i] = quickPow(i, p - 2, p);
    }
}

int inv(int x) {
    return vec[x];
}