#include "inv.h"
#include <bits/stdc++.h>

using namespace std;

//预处理 Farey 序列 $F_{ \sqrt[3]{p} }$ 和 $\sqrt[3]{p}^2$ 内数的逆元
int n, m, P; vector<int> F, init_inv;  // n = \sqrt[3]{p}, m = n^2
vector<int> sum, frac;
inline long long ksm(long long a, int b, int Mod) {
    long long r = 1;
    while(b) {
        if(b & 1) r = r * a % Mod;
        b >>= 1, a = a * a % Mod;
    }
    return r;
}

void init(int p) {
    ::P = p, n = (int)pow(p, 1.0 / 3) + 2; m = n * n;
    sum = vector<int>(m + 1, 0), frac = vector<int>(m + 1, 0), init_inv.resize(m + 1);

    // 根据 (\lfloor x / y \times n^2) \rfloor 互不相同预处理Farey序列
    for(int x = 1; x <= n - 1; x ++) for(int y = 0; y <= x; y ++) {
        int i = y * m / x; if(!sum[i]) sum[i] = 1, frac[i] = y * n + x;
    }
    for(int i = 1; i <= m; i ++) sum[i] += sum[i - 1];
    for(int i = 0; i <= m; i ++) if(frac[i]) F.emplace_back(frac[i]);
    
    init_inv[1] = 1;
    vector<int> d(m + 1, 0), primes;
    for(int i = 2; i <= m; i ++) {
        if(!d[i]) primes.emplace_back(i), init_inv[i] = ksm(i, p - 2, p);
        for(auto pr : primes) {
            if(1ll * pr * i > m) break;
            d[pr * i] = pr, init_inv[pr * i] = 1ll * init_inv[pr] * init_inv[i] % P;
            if(i % pr == 0) break;
        }
    }
}
int inv(int x) {
    int i = 1ll * x * m / P, k = sum[i]; long long f, t; int p, q;
    if(k < F.size()) {
        f = F[k], p = f / n, q = f - n * p, t = 1ll * x * q - 1ll * p * P;
        if(abs(t) <= m) return 1ll * q * (t > 0 ? init_inv[t] : P - init_inv[-t]) % P;
    }
    if(--k >= 0) {
        f = F[k], p = f / n, q = f - n * p, t = 1ll * x * q - 1ll * p * P;
        if(abs(t) <= m) return 1ll * q * (t > 0 ? init_inv[t] : P - init_inv[-t]) % P;
    }
    return -1;
}