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

// 2023 OneWan

struct Inverse {
	int B, B2, mod;
	vector<int> inv, pre, suf;
	vector<pair<int, int>> s;
	Inverse() = default;
	Inverse(int mod) : mod(mod) {
		B = pow(mod, 0.3333333333);
		B2 = B * B;
		inv.resize(mod / B + 1);
		inv[1] = 1;
		for (int i = 2, j = mod / B ; i <= j ; i++) {
			inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
		}
		s.resize (B2 + 1);
		pre.resize(B2 + 1);
		suf.resize(B2 + 1);
		s[0] = {0, 1};
		s[B2] = {1, 1};
		pre[B2] = suf[B2] = B2;
		for (int i = 2 ; i <= B ; i++) {
			for (int j = 1 ; j < i ; j++) {
				int pos = 1LL * j * B2 / i;
				if (pre[pos]) continue;
				pre[pos] = suf[pos] = pos;
				s[pos] = {j, i};
			}
		}
		for (int i = 1 ; i <= B2 ; i++) {
			if (pre[i] == 0) {
				pre[i] = pre[i - 1];
			}
		}
		for (int i = B2 ; i > 0 ; i--) {
			if (suf[i] == 0) {
				suf[i] = suf[i + 1];
			}
		}
	}
	int calc(int T, pair<int, int> x) {
		long long pos = 1LL * T * x.second;
		if (llabs(pos - 1LL * mod * x.first) > mod / B) return -1;
		pos %= mod;
		if (pos <= mod / B) return 1LL * x.second * inv[pos] % mod;
		return mod - 1LL * x.second * inv[mod - pos] % mod;
	}
	int operator()(int x) {
		x %= mod;
		if (x <= mod / B) return inv[x];
		int pos = 1LL * x * B2 / mod, res = calc(x, s[pre[pos]]);
		if (res == -1) res = calc(x, s[suf[pos]]);
		return res;
	}
};

Inverse invs;

void init(int p) {
	invs = Inverse(p);
}

int inv(int x) {
	return invs(x);
}