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

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);
        B = max(1000, B);
        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

Inverse invs;

void init(int p) {
	invs = Inverse(998244353);
}
int inv(int x) {
	assert(x <= 1000000000);
	return invs(x);
}