#include "inv.h"
#include <array>
#include <vector>
#include <iostream>

using i64 = long long;

constexpr int P = 998244353;

namespace Inversion {

	static constexpr int B = (1 << 10), T = (1 << 20);

	std::array<int, T + 1> f, p;
	std::array<int, T * 3 + 3> buf;

	int *I = buf.begin() + T;

	void init() {
		for (int i = 1; i <= B; i++) {
			int s = 0, d = (i << 10);
			for (int j = 1; j <= T; j++) {
				if ((s += d) >= P) s -= P;
				if (s <= T) {
					if (!f[j]) f[j] = i, p[j] = s;
				} 
				else if (s >= P - T) {
					if (!f[j]) f[j] = i, p[j] = s - P;
				} 
				else {
					int t = (P - T - s - 1) / d;
					s += t * d, j += t;
				}
			}
		}

		I[1] = f[0] = 1;
		for (int i = 2; i <= (T << 1); i++)
			I[i] = 1ll * (P - P / i) * I[P % i] % P;

		for (int i = -1; i >= -T; i--)
			I[i] = P - I[-i];
	}

	int inv(int x) {
		return 1ll * I[p[x >> 10] + (x & 1023) * f[x >> 10]] * f[x >> 10] % P;
	}
};

void init(int p) {
	Inversion::init();
}

int inv(int x) {
	return Inversion::inv(x);
}