#include "inv.h"

const int n = 1e8;
int res[n + 1];
void init(int p) {
    res[1] = 1;
    for (int i = 2; i <= n; i++) {
        res[i] = 1ll * (p - p / i) * res[p % i] % p;
    }
}

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