#include<iostream>
#include<cstdio>
#define mod 998244353
#define N 31595
using namespace std;
int MD2(int x)
{
	return x<0?x+mod:x;
}
int T,invs[N+1];
void init(int p)
{
	invs[1]=1;
	for (int i=2;i*i<=mod;++i) invs[i]=MD2(-1ll*(mod/i)*invs[mod%i]%mod);
	return;
}
int inv(int x)
{
	int a,b;
	if (1ll*x*x<=mod) return invs[x];
	else
	{
		a=mod/x,b=mod%x;
		if ((b<<1)<=x) return 1ll*MD2(-a)*inv(b)%mod;
		else return 1ll*(a+1)*inv(x-b)%mod;
	}
}