RT。

在写本题并调试的时候，打出中间变量时意外通过了本题......

我也不知道我卷了些什么，但是我显然没有像题解那样卷分子，求证下面代码的正确性。

如果能给出推导就更好了/qq

#include<iostream>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<cstdlib>
#include<queue>
#include<math.h>
#include<time.h>
#include<set>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct fastIO{
	bool digit(char ch){
		return ch>='0'&&ch<='9';
	}
	fastIO(){}
	fastIO &operator>>(char *s){
		int len=0;
		char ch=getchar();
		while(ch==' '||ch=='\n') ch=getchar();
		while(ch!=' '&&ch!='\n'&&ch!='\r') s[len++]=ch,ch=getchar();
		return *this;
	}
	template<typename T>
	fastIO &operator>>(T &res){
		res=0;
		bool flag=0;
		char ch=getchar();
		while(!digit(ch)) flag=(ch=='-'||flag),ch=getchar();
		while(digit(ch)) res=res*10+ch-'0',ch=getchar();
		if(ch!='.'){
			res=flag?-res:res;
			return *this;
		}
		double base=0.1;
		while(!digit(ch)) ch=getchar();
		while(digit(ch)) res+=base*(ch-'0'),base/=10.0,ch=getchar();
		res=flag?-res:res;
		return *this;
	}
	fastIO &operator<<(char ch){
		putchar(ch);
		return *this;
	}
	fastIO &operator<<(const char *s){
		int len=strlen(s);
		for(int i=0;i<len;i++) putchar(s[i]);
		return *this;
	}
	fastIO &operator<<(string s){
		int len=s.length();
		for(int i=0;i<len;i++) putchar(s[i]);
		return *this;
	}
	char OUT_Put[105];
	template<typename T>
	fastIO &operator<<(T x){
		if(x<0) putchar('-'),x=-x;
		if(x==0) return putchar('0'),*this;
		int i=0;
		while(x) OUT_Put[++i]=x%10+'0',x/=10;
		while(i) putchar(OUT_Put[i--]);
		return *this;
	}
}io;
#define N 500005 
#define p 998244353
#define G 3
#define invG 332748118
int rev[N];
inline int add(int a,int b){
	return (a+b>=p?a+b-p:a+b);
}
inline int mul(int a,int b){
	return (long long)a*b%p;
}
inline int power(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=mul(res,x);
		x=mul(x,x),y>>=1; 
	}
	return res;
}
inline void NTT(int *c,int len,int typ){
	for(int i=0;i<len;i++)
		if(i<rev[i]) swap(c[i],c[rev[i]]);
	for(int arc=1;arc<len;arc<<=1){
		int base=power(!typ?invG:G,(p-1)/(arc<<1));
		for(int i=0;i<len;i+=arc<<1)
			for(int j=0,now=1;j<arc;j++,now=mul(now,base)){
				int x=c[i+j],y=mul(now,c[i+j+arc]);
				c[i+j]=add(x,y),c[i+j+arc]=add(x,p-y);
			}
	}
	if(!typ){
		int invl=power(len,p-2);
		for(int i=0;i<len;i++) c[i]=mul(c[i],invl);
	}
} 
#undef G
#undef invG
int tmp[N];
inline void poly_inv(int n,int *f,int *g){
	if(!n) return g[0]=1,void();
	poly_inv(n>>1,f,g);
	int len=1,bit=0;
	for(;len<=n+n;len<<=1,bit++);
	for(int i=0;i<len;i++)
		rev[i]=rev[i>>1]>>1|((i&1)<<(bit-1));
	for(int i=0;i<=n;i++) tmp[i]=f[i];
	for(int i=n+1;i<len;i++) tmp[i]=0;
	NTT(tmp,len,1),NTT(g,len,1);
	for(int i=0;i<len;i++) g[i]=mul(g[i],add(2,p-mul(g[i],tmp[i])));
	NTT(g,len,0);
	for(int i=n+1;i<len;i++) g[i]=0;
}
int fac[N],inv[N],n=100000,T,f[N],g[N],F[N],G[N];
int main(){
	io>>T;
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++) 
		fac[i]=mul(fac[i-1],i),
		inv[i]=mul(p-p/i,inv[p%i]);
	for(int i=2;i<=n;i++) inv[i]=mul(inv[i],inv[i-1]);
	for(int i=0;i<=n;i++) G[i]=add(p-inv[i],0),F[i]=inv[i];
	G[0]=add(G[0],2),F[0]--;
	poly_inv(n,G,g);
	for(int i=0;i<=n;i++) f[i]=g[i];
	int len=1,bit=0;
	for(;len<=n+n;len<<=1,bit++);
	for(int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)<<(bit-1));
	NTT(f,len,1),NTT(F,len,1);
	for(int i=0;i<len;i++) f[i]=mul(f[i],f[i]);
	NTT(f,len,0);
	
	while(T--) io>>n,io<<mul(f[n],power(g[n],p-2))-1<<'\n';
	return 0;
}