#include "inv.h"

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); }

implementer.cpp: In function ‘int main()’:
implementer.cpp:22:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
answer.code:6:33: error: there are no arguments to ‘pow’ that depend on a template parameter, so a declaration of ‘pow’ must be available [-fpermissive]
    6 |   static constexpr int n = ceil(pow(p, 1.0 / 3));
      |                                 ^~~
answer.code:6:33: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
answer.code: In member function ‘int Inverse_O1<MOD>::inv(int)’:
answer.code:36:9: error: there are no arguments to ‘abs’ that depend on a template parameter, so a declaration of ‘abs’ must be available [-fpermissive]
   36 |     if (abs(u) <= n2) {
      |         ^~~
answer.code: In instantiation of ‘constexpr const int Inverse_O1<998244353>::n’:
answer.code:7:29:   required from ‘constexpr const int Inverse_O1<998244353>::n2’
answer.code:10:11:   required from ‘struct Inverse_O1<998244353>’
answer.code:46:23:   required from here
answer.code:6:36: error: ‘pow’ was not declared in this scope
    6 |   static constexpr int n = ceil(pow(p, 1.0 / 3));
      |                                 ~~~^~~~~~~~~~~~
answer.code:6:32: error: ‘ceil’ was not declared in this scope
    6 |   static constexpr int n = ceil(pow(p, 1.0 / 3));
      |                            ~~~~^~~~~~~~~~~~~~~~~
answer.code: In instantiation of ‘struct Inverse_O1<998244353>’:
answer.code:46:23:   required from here
answer.code:10:14: error: size of array is not an integral constant-expression
   10 |   int pre[n2 + 1], suf[n2 + 1], preinv[n2 + 10];
      |           ~~~^~~
answer.code:10:27: error: size of array is not an integral constant-expression
   10 |   int pre[n2 + 1], suf[n2 + 1], preinv[n2 + 10];
      |                        ~~~^~~
answer.code:10:43: error: size of array is not an integral constant-expression
   10 |   int pre[n2 + 1], suf[n2 + 1], preinv[n2 + 10];
      |                                        ~~~^~~~
answer.code: In instantiation of ‘int Inverse_O1<MOD>::inv(int) [with int MOD = 998244353]’:
answer.code:43:34:   required from ‘int Inverse_O1<MOD>::operator()(int) [with int MOD = 998244353]’
answer.code:48:31:   required from here
answer.code:36:12: error: ‘abs’ was not declared in this scope
   36 |     if (abs(u) <= n2) {
      |         ~~~^~~