#include "inv.h"

#include<cmath>
using namespace std;

template <int MOD>
struct Inverse_O1 {
  static constexpr int p = MOD;
  static constexpr int n = ceil(pow(p, 1.0 / 3));
  static constexpr int n2 = n * n;
  static constexpr int shift = 16;

  int pre[n2 + 1], suf[n2 + 1], preinv[n2 + 10];
  Inverse_O1() {
    for (int i = 0; i <= n2; i++) pre[i] = suf[i] = 0;
    for (int y = 1; y < n; y++) {
      for (int x = 0; x <= y; x++) {
        int z = x * n2 / y;
        if (!pre[z]) pre[z] = suf[z] = (x << shift) + y;
      }
    }
    for (int i = 1; i <= n2; i++) {
      if (!pre[i]) pre[i] = pre[i - 1];
    }
    for (int i = n2 - 1; i >= 0; i--) {
      if (!suf[i]) suf[i] = suf[i + 1];
    }
    preinv[0] = preinv[1] = 1 % p;
    for (int i = 2; i < n2 + 10; i++) {
      preinv[i] = 1LL * preinv[p % i] * (p - p / i) % p;
    }
  }

  int inv(int a) {
    if (a <= n2) return preinv[a];
    int i = 1LL * a * n2 / p, x, y, u;
    x = pre[i] >> shift, y = pre[i] & ((1 << shift) - 1);
    u = 1LL * a * y - 1LL * p * x;
    if (abs(u) <= n2) {
      return 1LL * (u < 0 ? p - preinv[-u] : preinv[u]) * y % p;
    }
    x = suf[i] >> shift, y = suf[i] & ((1 << shift) - 1);
    u = 1LL * a * y - 1LL * p * x;
    return 1LL * (u < 0 ? p - preinv[-u] : preinv[u]) * y % p;
  }
  int operator()(int a) { return inv(a); }
};

Inverse_O1<998244353> inv_o1;
void init(int) {}
int inv(int x) { return inv_o1(x); }