#pragma once
#pragma GCC optimize("Ofast, unroll-loops")
#include "inv.h"
int a[3035136], g[974849];
int inv(int x) {
	const int p = (unsigned long long) x * g[x >> 10] % 998244353;
	return (unsigned long long) g[x >> 10] * (p < 3035136 ? a[p] : 998244353 - a[998244353 - p]) % 998244353;
}
int getinv(int x) {
    return x == 1 ? 1 : 974849 - (unsigned long long)(974849 / x) * getinv(974849 % x) % 974849;
}
void init(int) {
	for(int i = 987;i;--i) {
		int inv = getinv(i);
		for(int j = 1;j <= 987;++j) {
			g[(unsigned long long) j * inv % 974849] = i;
			g[974849 - (unsigned long long) j * inv % 974849] = 998244353 - i;
		}
	}
	g[0] = a[1] = 1;
	for(int i = 2;i ^ 3035136;++i)
		a[i] = 998244353 - (unsigned long long)(998244353 / i) * a[998244353 % i] % 998244353;
}