这题推出平方的转移式不难，但是进一步优化需要技巧。

首先把 ”不全红“ 和”不全蓝“的限制去掉。

其次，对于一个完全图，它如果不 红边连通，蓝边连通。

这个证明是容易的，假设一个完全图有两个点集 ， 与 之间没有红边，那么对于任意 ，， 之间都会有一条蓝边，那么这个图显然会被蓝边连通。

那我们只需要保证红蓝不同时连通即可。

设 表示一个 个点的完全图由红边连通的方案数，那么 。

考虑转移，既然这张图蓝边不连通，那么我们枚举 号点所在的蓝边连通块大小，设为 ，那么会有 种方案选出这个连通块，块内的方案数是 ，块外的方案数是 ，块内与块外之间的边必须都是红边，故系数为 。另外，如果 ，方案数还要乘 ，因为块外的图既可以红连通，也可以蓝连通。

直接转移即可通过 F1。

考虑优化转移的复杂度，把转移式写出来。 写得好看一些： 令 那么 。

把组合数拆开： 设 。

那么

这看上去就像分治 FFT 的式子，但我们发现 和 都需要由卷积的结果推出，而一般的分治 FFT 中， 这个位置放的是个已知序列。

考虑一般的分治 FFT,我们是用 与 进行卷积，并将结果加到右区间对应的位置。

考虑这个方法什么时候会出问题，这种情况会出现当且仅当 ，即 ，即 。

这种情况只会在 时出现，因为在分治树上第一次往右走时，就有 ，此后 不降， 不增，自然也不会出问题。

考虑把分治 FFT 的贡献拆成三部分： 第一部分的贡献可以在 那里就算完了，第二部分和第三部分的贡献形式是相同的，可以在 的区间里一起计算这两类贡献。

具体的可以看代码，时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,P = 998244353,GG = 3;
inline int Add(const int &a,const int &b) { return (a + b >= P) ? (a + b - P) : (a + b);}
inline int Sub(const int &a,const int &b) { return (a < b) ? (a - b + P) : (a - b);}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
const int Gi = qpow(GG,P - 2);
int n;
int Gs[N],Gs2[N],rev[N];
inline int GetLen(int x)
{
	int len = 1;
	while(len <= x) len <<= 1;
	return len;
}
inline void calc_rev(int len)
{
	for(int i = 0;i < len;i++)
	{
		rev[i] = rev[i >> 1] >> 1;
		if(i & 1) rev[i] |= len >> 1;
	}
}
int fac[N],ifac[N];
inline void init(int len)
{
	for(int i = 1;i < len;i <<= 1)
	{
		Gs[i] = Gs2[i] = 1;
		Gs[i + 1] = qpow(GG,(P - 1) / (i << 1));
		Gs2[i + 1] = qpow(Gi,(P - 1) / (i << 1));
		for(int j = 2;j < i;j++)
			Gs[i + j] = 1ll * Gs[i + j - 1] * Gs[i + 1] % P,
			Gs2[i + j] = 1ll * Gs2[i + j - 1] * Gs2[i + 1] % P;
	}
	fac[0] = 1;
	for(int i = 1;i <= len;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[1] = 1;
	for(int i = 2;i <= len;i++) ifac[i] = 1ll * ifac[P % i] * (P - P / i) % P;
	ifac[0] = 1;
	for(int i = 1;i <= len;i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % P;
}
inline void NTT(int *F,int len,int type)
{
	for(int i = 0;i < len;i++)
		if(i < rev[i]) swap(F[i],F[rev[i]]);
	for(int k = 1;k < len;k <<= 1)
		for(int j = 0;j < len;j += k + k)
			for(int i = 0;i < k;i++)
			{
				int cur = type == 1 ? Gs[k | i] : Gs2[k | i];
				int u = F[i | j],v = 1ll * cur * F[i | j | k] % P;
				F[i | j] = Add(u,v);
				F[i | j | k] = Sub(u,v);
			}
	if(type == -1)
		for(int i = 0,Inv = qpow(len,P - 2);i < len;i++)
			F[i] = 1ll * F[i] * Inv % P;
}
int A[N],B[N];

int f[N],F[N],G[N];
void cdq(int l,int r)
{
	if(l == r)
	{
		if(l > 1)
		{
			f[l] = 2ll * f[l] * fac[l - 1] % P;
			f[l] = Sub(f[l],1ll * (l - 1) * f[l - 1] % P);
			F[l] = 1ll * f[l] * ifac[l - 1] % P;
			G[l] = 1ll * f[l] * ifac[l] % P;
		}
		return;
	}
	int mid = l + r >> 1;
	cdq(l,mid);
	if(l == 1)
	{
		int len = GetLen((mid - l + 1) + (mid - l + 1)); // 第一部分
		for(int i = 0;i < len;i++) A[i] = B[i] = 0;
		for(int i = 0;i <= mid - l;i++)
			A[i] = F[i + 1],B[i] = G[i + 1];
		calc_rev(len);
		NTT(A,len,1);NTT(B,len,1);
		for(int i = 0;i < len;i++) A[i] = 1ll * A[i] * B[i] % P;
		NTT(A,len,-1);
		for(int i = mid + 1;i <= r;i++)
			f[i] = Add(f[i],A[i - 2]);
	}
	else // 第二部分和第三部分
	{
		int len = GetLen((r - l + 1) + (mid - l + 1));
		for(int i = 0;i < len;i++) A[i] = B[i] = 0;
		for(int i = 0;i < r - l;i++)
			A[i] = F[i + 1];
		for(int i = 0;i <= mid - l;i++)
			B[i] = G[i + l];
		calc_rev(len);
		NTT(A,len,1);NTT(B,len,1);
		for(int i = 0;i < len;i++) A[i] = 1ll * A[i] * B[i] % P;
		NTT(A,len,-1);
		for(int i = mid + 1;i <= r;i++)
			f[i] = Add(f[i],A[i - l - 1]);
		for(int i = 0;i < len;i++) A[i] = B[i] = 0;
		for(int i = 0;i < r - l;i++)
			A[i] = G[i + 1];
		for(int i = 0;i <= mid - l;i++)
			B[i] = F[i + l];
		calc_rev(len);
		NTT(A,len,1);NTT(B,len,1);
		for(int i = 0;i < len;i++) A[i] = 1ll * A[i] * B[i] % P;
		NTT(A,len,-1);
		for(int i = mid + 1;i <= r;i++)
			f[i] = Add(f[i],A[i - l - 1]);
	}
	cdq(mid + 1,r);
}
int main()
{
	cin >> n;
	f[1] = F[1] = G[1] = 1;
	int len = GetLen(n * 2);
	init(len);
	cdq(1,n);
	cout << ((f[n] - 1) * 2ll) % P << endl;
	return 0;
}