#include "inv.h"

constexpr int mod = 998244353;
constexpr int n = pow(mod, 1.0 / 3);
constexpr int n2 = n * n;
constexpr int mod_n = mod / n;

int p[n2 + 1];
int f[n2 + 1];
int inv[mod_n + 1];

void init(int _p) {
	assert(_p == mod);

	for (int y = 1; y <= n; y++) {
		for (int x = 0; x <= y; x++) {
			int i = x * n2 / y;
			if (!p[i]) {
				p[i] = x * n + y;
			}
		}
	}

	int f_cnt = 0;
	for (int i = 0; i <= n2; i++) {
		if (p[i]) {
			f[f_cnt++] = p[i];
		}
		p[i] = f_cnt;
	}

	inv[1] = 1;
	for (int i = 2; i <= mod_n; i++)
		inv[i] = mod - (long long) (mod / i) * inv[mod % i] % mod;
}

int inv(int a) {
	int i = p[(long long) a * n2 / mod];
	int x = f[i] / n;
	int y = f[i] % n;
	int u = a * y - mod * x;

	if (abs(u) > mod_n) {
		i--;
		x = f[i] / n;
		y = f[i] % n;
		u = a * y - mod * x;
	}

	return (long long) y * (u < 0 ? mod - inv[-u] : inv[u]) % mod;
}

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:4:19: error: ‘pow’ was not declared in this scope
    4 | constexpr int n = pow(mod, 1.0 / 3);
      |                   ^~~
answer.code:8:10: error: size of array ‘p’ is not an integral constant-expression
    8 | int p[n2 + 1];
      |       ~~~^~~
answer.code:9:10: error: size of array ‘f’ is not an integral constant-expression
    9 | int f[n2 + 1];
      |       ~~~^~~
answer.code:10:15: error: size of array ‘inv’ is not an integral constant-expression
   10 | int inv[mod_n + 1];
      |         ~~~~~~^~~
answer.code:10:18: error: ‘int inv [1]’ redeclared as different kind of entity
   10 | int inv[mod_n + 1];
      |                  ^
In file included from answer.code:1:
inv.h:2:5: note: previous declaration ‘int inv(int)’
    2 | int inv(int n);
      |     ^~~
answer.code: In function ‘void init(int)’:
answer.code:13:9: error: ‘assert’ was not declared in this scope
   13 |         assert(_p == mod);
      |         ^~~~~~
answer.code:2:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
    1 | #include "inv.h"
  +++ |+#include <cassert>
    2 | 
answer.code:32:14: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   32 |         inv[1] = 1;
      |              ^
answer.code:32:16: error: assignment of read-only location ‘*(inv + 1)’
   32 |         inv[1] = 1;
      |         ~~~~~~~^~~
answer.code:34:22: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   34 |                 inv[i] = mod - (long long) (mod / i) * inv[mod % i] % mod;
      |                      ^
answer.code:34:67: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   34 |                 inv[i] = mod - (long long) (mod / i) * inv[mod % i] % mod;
      |                                                                   ^
answer.code:34:54: error: invalid operands of types ‘long long int’ and ‘int(int)’ to binary ‘operator*’
   34 |                 inv[i] = mod - (long long) (mod / i) * inv[mod % i] % mod;
      |                                ~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~~~~~~~~
      |                                |                                  |
      |                                long long int                      int(int)
answer.code: In function ‘int inv(int)’:
answer.code:43:13: error: ‘abs’ was not declared in this scope
   43 |         if (abs(u) > mod_n) {
      |             ^~~
answer.code:50:53: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   50 |         return (long long) y * (u < 0 ? mod - inv[-u] : inv[u]) % mod;
      |                                                     ^
answer.code:50:45: error: invalid operands of types ‘const int’ and ‘int(int)’ to binary ‘operator-’
   50 |         return (long long) y * (u < 0 ? mod - inv[-u] : inv[u]) % mod;
      |                                         ~~~ ^ ~~~~~~~
      |                                         |           |
      |                                         const int   int(int)
answer.code:50:62: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   50 |         return (long long) y * (u < 0 ? mod - inv[-u] : inv[u]) % mod;
      |                                                              ^