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

namespace MyNamespace {
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 po;
typedef unsigned __int128 upo;

inline namespace MyIO {
	inline ll rd() {
		char ch = getchar();
		ll s = 0, w = 1;
		while (!isdigit(ch)) {
			if (ch == '-') w = -1;
			ch = getchar();
		}
		while (isdigit(ch)) {
			s = (s << 3) + (s << 1) + (ch ^ 48);
			ch = getchar();
		}
		return (s * w);
	}
	template<typename T>
	inline void wr(T x) {
		if (x < 0) x = -x, putchar('-');
		if (x > 9) wr(x / 10);
		putchar(x % 10 + 48);
	}
	inline void wrsp() {
		// pass
	}
	template<typename T, typename... Args>
	inline void wrsp(T x, Args... args) {
		wr(x), putchar(' '), wrsp(args...);
	}
	inline void wrln() {
		putchar('\n');
	}
	template<typename T>
	inline void wrln(T x) {
		wr(x), putchar('\n');
	}
	template<typename T, typename... Args>
	inline void wrln(T x, Args... args) {
		wr(x), putchar(' '), wrln(args...);
	}
} // namespace MyIO

inline namespace Base {
	#define bug(x) << #x << '=' << (x) << ' '
	#define siz(A) ll((A).size())

	template<typename T>
	constexpr inline T& Max(T &x, const T &y) {
		return x = max(x, y);
	}
	template<typename T>
	constexpr inline T& Min(T &x, const T &y) {
		return x = min(x, y);
	}
} // namespace Base

namespace {
	ll MO;
	inline ll moa(ll x) {
		return (x >= MO ? x - MO : x);
	}
	inline ll moi(ll x) {
		return (x < 0 ? x + MO : x);
	}
	inline ll mo(ll x) {
		return moi((x) % MO);
	}
	inline ll& Moa(ll &x) {
		return x = moa(x);
	}
	inline ll& Moi(ll &x) {
		return x = moi(x);
	}
	inline ll& Mo(ll &x) {
		return x = mo(x);
	}
}

struct Barrett {
	ull MO, u;
	Barrett() {}
	Barrett(ull _MO) {
		MO = _MO;
		u = (upo(1) << 64) / MO;
	}
	inline ll operator () (ll x) {
		ull q = (po(x) * u) >> 64;
		ull r = x - q * MO;
		return (r >= MO ? r - MO : r);
	}
	inline ll operator [] (ll x) {
		ull q = (po(x) * u) >> 64;
		return q + (x - q * MO >= MO);
	}
} mod;
inline ll& Mod(ll &x) {
	return x = mod(x);
}

namespace {
	inline ll qpow(ll x, ll y) {
		Mo(x);
		ll k = 1;
		while (y) {
			if (y & 1) Mod(k *= x);
			Mod(x *= x);
			y >>= 1;
		}
		return k;
	}
	inline ll get_inv(ll x) {
		return qpow(x, MO - 2);
	}
}

constexpr ll B = 1000, fsqB = 1e6 + 10;
constexpr ll BK = B + 10, sqB = fsqB + 10;

ll inv[sqB];
ll nume[sqB], deno[sqB];
ll pre[sqB], nxt[sqB];

void init(ll _MO) {
	MO = _MO;
	new(&mod) Barrett(MO);

	inv[0] = inv[1] = 1;
	for (ll i = 2; i <= fsqB; ++i) 
		inv[i] = mod((MO - MO / i) * inv[MO % i]);

	tie(nume[0], deno[0]) = make_tuple(0, 1);
	tie(nume[B * B], deno[B * B]) = make_tuple(1, 1);
	for (ll i = 2; i <= B; ++i) 
		for (ll j = 1; j < i; ++j) {
			ll v = j * B * B / i;
			if (!deno[v]) 
				tie(nume[v], deno[v]) = make_tuple(j, i);
		}

	for (ll i = 0, lst = 0; i <= fsqB; ++i) {
		if (deno[i]) lst = i;
		pre[i] = lst;
	}
	for (ll i = fsqB, lst = fsqB; i >= 0; --i) {
		if (deno[i]) lst = i;
		nxt[i] = lst;
	}
}

inline ll calc(ll x, ll v) {
	ll d = deno[v] * x - nume[v] * MO;
	if (abs(d) > fsqB) return -1;
	if (d >= 0) return mod(inv[d] * deno[v]);
	else return moi(-mod(inv[-d] * deno[v]));
}
inline ll lget_inv(ll x) {
	if (x <= fsqB) return inv[x];
	if (moi(-x) <= fsqB) return moi(-inv[moi(-x)]);
	ll v = x * B * B / MO;
	ll res = calc(x, pre[v]);
	if (~res) return res;
	else return calc(x, nxt[v]);
}
} // namespace MyNamespace

void init(int p) {
	MyNamespace::init(p);
}

int inv(int x) {
	return MyNamespace::lget_inv(x);
}