传送门

题目大意：

[图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/equation-1024x94.png

答案一定是一个有理数，以n=p·q-1的形式并模上998244353给出。 q-1 表示q的逆元，可以用扩欧或费马小定理来算。

如果p是一个质数，而整数a不是p的倍数，则有a(p-1)≡1(mod p)

费马小定理

有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是显然地。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解，它可以用来计算模反元素(也叫模逆元)。

扩展欧几里得算法

[图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_390520200714-224509-1024x931.jpg

#include<bits/stdc++.h>

using namespace std;  

typedef long long ll;

int const LIM = 2e6 + 5;  
int const MOD = 998244353;

ll n;
ll fac[LIM];
  
ll qmod(ll x, ll y)
{
    ll res = 1;  
    
	while (y) 
	{
        if(y & 1) 
			res = (1ll * res * x) % MOD;  
        y >>= 1; 
        x = (1ll * x * x) % MOD;  
    }
    
    return res;  
}

int main()
{
    fac[0] = 1;  
	for(ll i = 1; i < LIM; i++)
        fac[i] = (1ll * fac[i-1] * i) % MOD;  
    
	while (cin >> n)
        printf("%lld\n", (1ll * fac[n] * fac[n]) % MOD * qmod(fac[2*n+1], MOD - 2) % MOD);  
    
	return 0; 
}