#include "inv.h"
typedef unsigned ui;
typedef __uint128_t L;
typedef unsigned long long ull;
const ui MOD=998244353,M1=1000,M2=M1*M1;
const double invM1=1./M1+1e-15,INV=1.*M2/MOD+1e-15;
ui T,len,fra[M2+5],Inv[M2+5],sum[M2+5];
ui q[M2+5];ull p[M2+5];
struct FastMod{
	ull b,m;
	FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
	friend inline ull operator%(const ull&a,const FastMod&mod){
		ull r=a-(L(mod.m)*a>>64)*mod.b;
		return r>=mod.b?r-mod.b:r;
	}
}mod(MOD);
inline ull abs(const ull&a){
	return a>>63?-a:a;
}
inline void Init(){
	ui i,j,x;
	for(i=1;i^M1;++i){
		const double&INV=1./i+1e-15;
		for(j=0;j^i;++j)if(!sum[x=1ull*j*M2*INV])sum[x]=1,fra[x]=M1*i+j;
	}
	for(i=0;i<=M2;++i){
		if(sum[i])++len,q[len]=fra[i]*invM1,p[len]=1ull*(fra[i]-q[len]*M1)*MOD;
		if(i)sum[i]+=sum[i-1];Inv[i]=i>1?1ull*(MOD-MOD/i)*Inv[MOD%i]%mod:i;
	}
}
inline ui Qry(const ui&a){
	static ui q,k;static ull t;
	if(a<=M2)return Inv[a];if(MOD-a<=M2)return MOD-Inv[MOD-a];k=sum[ui(a*INV)];
	if(k<=len){
		q=::q[k];t=1ull*a*q-p[k];
		if(abs(t)<=M2)return 1ull*q*(t>>63?MOD-Inv[-t]:Inv[t])%mod;
	}
	if(++k<=len){
		q=::q[k];t=1ull*a*q-p[k];
		if(abs(t)<=M2)return 1ull*q*(t>>63?MOD-Inv[-t]:Inv[t])%mod;
	}
	return-1;
}
void init(int p){
	Init();
}
int inv(int x){
	return Qry(x);
}