//Let's join Kaede Takagaki Fan Club !! #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long //#define L __int128 typedef long long ll; typedef pair P; typedef pair P1; typedef pair P2; #define pu push #define pb push_back #define eb emplace_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define a first #define b second #define fi first #define sc second //#define rng(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,x) for(int i=0;i bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b using vc=vector; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os<> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } //don't make x negative! size_t operator()(pair x)const{ return operator()(uint64_t(x.first)<<32|x.second); } }; //unordered_set -> dtype, null_type //unordered_map -> dtype(key), dtype(value) using namespace __gnu_pbds; template using hash_table=gp_hash_table; template void g(T &a){ cin >> a; } template void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 998244353; //const ll mod = 1000000007; mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); template void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } ll modpow(ll a,ll n){ ll cur = a,ret = 1; while(n){ if(n%2 == 1) ret = ret*cur%mod; cur = cur*cur%mod; n /= 2; } return ret; } #define _sz 400005 ll F[_sz],R[_sz]; void make(){ F[0] = 1; for(int i=1;i<_sz;i++) F[i] = F[i-1]*i%mod; R[_sz-1] = modpow(F[_sz-1], mod-2); for(int i=_sz-2;i>=0;i--) R[i] = R[i+1] * (i+1) % mod; } ll C(int a,int b){ if(b < 0 || a < b) return 0; return F[a]*R[b]%mod*R[a-b]%mod; } const int md = 998244353; inline void add(int &a, int b) { a += b; if (a >= md) a -= md; } inline void sub(int &a, int b) { a -= b; if (a < 0) a += md; } inline int mul(int a, int b) { return (int) ((long long) a * b % md); } inline int power(int a, long long b) { int res = 1; while (b > 0) { if (b & 1) { res = mul(res, a); } a = mul(a, a); b >>= 1; } return res; } inline int inv(int a) { a %= md; if (a < 0) a += md; int b = md, u = 0, v = 1; while (a) { int t = b / a; b -= t * a; swap(a, b); u -= t * v; swap(u, v); } assert(b == 1); if (u < 0) u += md; return u; } namespace ntt { int base = 1; vector roots = {0, 1}; vector rev = {0, 1}; int max_base = -1; int root = -1; void init() { base = 1; roots = {0,1}; rev = {0,1}; max_base = -1; root = -1; int tmp = md - 1; max_base = 0; while (tmp % 2 == 0) { tmp /= 2; max_base++; } root = 2; while (true) { if (power(root, 1 << max_base) == 1) { if (power(root, 1 << (max_base - 1)) != 1) { break; } } root++; } } void ensure_base(int nbase) { if (max_base == -1) { init(); } if (nbase <= base) { return; } assert(nbase <= max_base); rev.resize(1 << nbase); for (int i = 0; i < (1 << nbase); i++) { rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1)); } roots.resize(1 << nbase); while (base < nbase) { int z = power(root, 1 << (max_base - 1 - base)); for (int i = 1 << (base - 1); i < (1 << base); i++) { roots[i << 1] = roots[i]; roots[(i << 1) + 1] = mul(roots[i], z); } base++; } } void fft(vector &a) { int n = a.size(); assert((n & (n - 1)) == 0); int zeros = __builtin_ctz(n); ensure_base(zeros); int shift = base - zeros; for (int i = 0; i < n; i++) { if (i < (rev[i] >> shift)) { swap(a[i], a[rev[i] >> shift]); } } for (int k = 1; k < n; k <<= 1) { for (int i = 0; i < n; i += 2 * k) { for (int j = 0; j < k; j++) { int x = a[i + j]; int y = mul(a[i + j + k], roots[j + k]); a[i + j] = x + y - md; if (a[i + j] < 0) a[i + j] += md; a[i + j + k] = x - y + md; if (a[i + j + k] >= md) a[i + j + k] -= md; } } } } vector multiply(vector a, vector b, int eq = 0) { int need = a.size() + b.size() - 1; int nbase = 0; while ((1 << nbase) < need) nbase++; ensure_base(nbase); int sz = 1 << nbase; a.resize(sz); b.resize(sz); fft(a); if (eq) b = a; else fft(b); int inv_sz = inv(sz); for (int i = 0; i < sz; i++) { a[i] = mul(mul(a[i], b[i]), inv_sz); } reverse(a.begin() + 1, a.end()); fft(a); a.resize(need); return a; } vector square(vector a) { return multiply(a, a, 1); } }; namespace power_series_master { //x^iの係数をvecc[i]にもつものとする //各々の処理はmod x^Mをサポートするものとする //add,sub,diff,intg,mul_int,mul,inv,sqrt,log,exp //add subでミスってたら流石に引退 //diff,intgも流石に大丈夫だと思うけど、diffに定数を噛ませて0を返す仕様で変なハマり方をしないか心配 //一番怖いのはlogで、手元でexpと組み合わせてテストしたら大丈夫そうだったけど、GP peterhof H でverifyしたいよね //mod は998244353固定なので、他の素数だった場合はmulをarbitrary_mod_convに変えないといけない //verify list //mul_int,sub,sqrt,inv... CF 438E //exp... yosupo judge #define vi vector vi init(vi a, int x){ a.resize(x,0); return a; } vi add(vi a, vi b,int M=-1){ if(a.size() < b.size()) swap(a,b); for(int i=0;i= mod) a[i] -= mod; } if(M >= 0 && a.size() > M) a.resize(M); return a; } vi sub(vi a, vi b,int M=-1){ if(a.size() < b.size()) a.resize(b.size(),0); for(int i=0;i= mod) a[i] -= mod; } if(M >= 0 && a.size() > M) a.resize(M); return a; } //微分 vi diff(vi a,int M=-1){ reverse(a.begin(),a.end()); a.pop_back(); reverse(a.begin(),a.end()); for(int i=0;i= 0 && a.size() > M) a.resize(M); if(a.empty()) a.pb(0); return a; } //積分、定数項は指定可能 vi intg(vi a,int coef=0,int M=-1){ reverse(a.begin(),a.end()); a.push_back(coef); reverse(a.begin(),a.end()); for(int i=1;i= 0 && a.size() > M) a.resize(M); return a; } vi mul_int(vi a,int x,int M=-1){ for(int i=0;i= 0 && a.size() > M) a.resize(M); return a; } vi mul(vi a,vi b,int M=-1){ //modが99...のときはnttできる //任意modの場合は、適当に区切ってもいいしgarnerしてもいいし任せます ntt::init(); a = ntt::multiply(a,b); if(M >= 0 && a.size() > M) a.resize(M); return a; } //vecで表される多項式の-1乗、x^(M-1)の項までを求めてM長のvectorを返す //ただし、vec[0] = 0の場合は無理 //r1(z)f(z) = x*? + 1 //rn(z)f(z) = x^n*? + 1とする //r(2n)(z) = 2*rn(z)-rn(z)^2f(z)とすればOK! vi inv(vi a,int M){ if(a.empty() || a[0] == 0) return vi(); //1の場合をやっておく vi r[30]; r[0].pb(modpow(a[0],mod-2)); int cur = 1; int nxt = 1; vi vec3; while(cur < M){ int nw = min(cur*2,(int)(a.size())); int sz = vec3.size(); vec3.resize(nw,0); for(int t=sz;t= M); r[nxt-1].resize(M); assert(r[nxt-1].size() == M); return r[nxt-1]; } //vecで表される多項式の平方根、x^(M-1)の項までを求めてM長のvectorを返す //ただし、vec[0] = 0の場合は無理 //整数の平方根求めるのかったるいのでそれはまた後日 //s1(z)^2 = f(z) (mod z) //sn(z)^2 = f(z) (mod z^n) とする //s(2n)(z) = 1/2 * (sn(z)+f(z)*sn(z)^-1) vi sqrt(vi a,int M){ if(a.empty() || a[0] == 0) return vi(); //1の場合をやっておく vi s[30]; //今日はvec[0] = 1のことしか考えません s[0].pb(1); assert(1LL*s[0][0]*s[0][0]%mod == a[0]); int cur = 1; int nxt = 1; vi vec3; while(cur < M){ int nw = min(cur*2,(int)(a.size())); int sz = vec3.size(); vec3.resize(nw,0); for(int t=sz;t= a.size()) aa.pb(0); else aa.pb(a[aa.size()]); } if(m>1){ vi w = add(q,mul(g,sub(diff(f,2*m-1),mul(f,q,2*m-1),2*m-1),2*m-1),2*m-1); f = add(f,mul(f,sub(aa,intg(w,0,2*m),2*m),2*m),2*m); } else{ vi w = mul(g,diff(f,2*m-1),2*m-1); f = add(f,mul(f,sub(aa,intg(w,0,2*m),2*m),2*m),2*m); } m*=2; while(q.size() < m-1){ if(q.size() >= h.size()) q.pb(0); else q.pb(h[q.size()]); } } f.resize(M); assert(f.size() == M); return f; } }; int n, k; //o(ans?"Yes":"No"); void solve(){ cin >> n >> k; make(); int ans = C(2*n, n); if(k == 1); else if(k == 2) ans = (ans+mod-2) % mod; else{ //k-3, k-2, k-1 vcpl[3]; rep(i, 3){ pl[i].resize(k, 0); for(int x=0;x> t; while(t--) solve(); }