#include <bits/stdc++.h>
#include "inv.h"
#define rep(i, a, b) for (int i = (a); i <= int(b); i++)
#define per(i, a, b) for (int i = (a); i >= int(b); i--)
#define fir first
#define sec second
#define tct template <class type>
using namespace std;

typedef long long ll;
const int M = 1e3, M2 = M * M;
int P, K = P / M;
int T, A, frac[M2 + 5], sum[M2 + 5], N, F[M2 + 5], I[1000005];

inline void red(int &x) { x += x >> 31 & P; }
tct inline void cmax(type &x, type y) { x < y ? x = y : 0; }
tct inline void cmin(type &x, type y) { x > y ? x = y : 0; }

inline int get(int x) { return x < 0 ? 0 : sum[x]; }
tct inline type my_abs(type x) { return x < 0 ? -x : x; }

int inv(int a) {
    static int x, y, u, v, w, p, q, k, d;
    static ll c;
    if (a <= K)
        return I[a];
    if (P - a <= K)
        return P - I[P - a];
    x = ll(M2) * a / P;
    y = get(x - 1);
    rep(i, 0, 114514) {
        u = i >> 1;
        if (i & 1) {
            v = y - u;
            if (v <= 0)
                continue;
            w = F[v];
        } else {
            v = A - y - u;
            if (v <= 0)
                continue;
            w = F[N + 1 - v];
        }
        q = w / M, p = w - M * q;
        c = ll(a) * q - ll(p) * P;
        if (my_abs(c) <= K) {
            k = q, d = c;
            break;
        }
    }
    return ll(k) * (d > 0 ? I[d] : P - I[-d]) % P;
}

 
void init(int p) 
{
	P = p; K = P / M;
    rep(q, 1, M) rep(p, 1, q - 1) {
        int i = ll(M2) * p / q;
        if (sum[i])
            continue;
        frac[i] = M * q + p, sum[i] = 1;
    }
    rep(i, 1, M2) if (sum[i]) F[++N] = frac[i];
    rep(i, 1, M2) sum[i] += sum[i - 1];
    A = sum[M2];
    I[1] = 1;
    rep(i, 2, K) I[i] = ll(P - P / i) * I[P % i] % P;
}