#include "inv.h"
#include <vector>
#include <iostream>
const int N = 1e7 + 10;
std::vector<int> vec(N);

void init(int p) {
    vec[1] = 1;
    for (int i = 2; i < N; i++) {
         vec[i] = p - p / i * vec[p % i] % p;
    }
}

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