#include <bits/stdc++.h>
#include "inv.h"
#define il inline
#define B __int128
using namespace std;
typedef long long ll;
const int mod=998244353;
il ll qp(ll a,ll b){
	ll ans=1ll;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod,b>>=1;
	}return ans;
}
const ll N=5e7+5;
int n,fac[N],iv[N],a[N],b[31];
void init(int MOD){
	n=N-5,fac[0]=1ll;for(int i=1;i<=n;++i) fac[i]=(1ll*fac[i-1]*i)%mod;
	iv[n]=qp(fac[n],mod-2ll);for(int i=n-1;i>=0;--i) iv[i]=(iv[i+1]*(i+1ll))%mod;
	for(int i=1;i<=n;++i) a[i]=(1ll*fac[i-1]*iv[i])%mod;
	for(int i=0;i<=29;++i) b[i]=qp(1ll<<i,mod-2ll);
}
int inv(int x){
	if(x<=n) return a[x];
	if(x&1){
		int y=mod/x;
		return 1ll*(mod-y)*inv(mod-x*y)%mod;
	}
	int y=__builtin_ctz(x);
	return 1ll*inv(x>>y)*b[y]%mod;
}
/*int main(){
	init(mod);
	mt19937 rnd(time(0));
	for(int i=1;i<=100;++i){
		int x=rnd()%(mod-1)+1;
		if(inv(x)!=qp(x,mod-2ll)) printf("%d %d %d\n",x,inv(x),qp(x,mod-2ll));
		//else puts("*");
	}
	return 0;
}*/