#include "inv.h"

#include <cmath>
#include <cassert>

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