#include<cmath>
#include<functional>
#include"inv.h"

const int mod = 998244353;
const int mod2 = 974849; 
const int w = sqrt(mod2);
const int limit = 3 * (w + 1) * 1024;
int djq[limit], arr[mod2];
using u64 = unsigned long long;
int inv(int x) {
	const int p = (u64) x * arr[x >> 10] % mod;
	return (u64) arr[x >> 10] * (p < limit ? djq[p] : mod - djq[mod - p]) % mod;
}
void init(int) {
	for(int i = w;i >= 1;--i) {
		std::function<int(int)> getinv = [&](int x) {
			return x == 1 ? 1 : mod2 - u64(mod2 / x) * getinv(mod2 % x) % mod2;
		};
		int inv = getinv(i);
		for(int j = 1;j <= w;++j) {
			arr[(u64) j * inv % mod2] = i;
			arr[mod2 - (u64) j * inv % mod2] = mod - i;
		}
	}
	arr[0] = 1, djq[1] = 1;
	for(int i = 2;i < limit;++i) {
		djq[i] = mod - u64(mod / i) * djq[mod % i] % mod;
	}
}