// g++-14 1.cpp -std=c++20 -O2 -I . #include using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include using namespace __gnu_pbds; #include #include using namespace atcoder; using ll = long long; using ld = long double; using vi = vector; using vvi = vector; using vll = vector; using vvll = vector; using vld = vector; using vvld = vector; using vst = vector; using vvst = vector; #define fi first #define se second #define pb push_back #define eb emplace_back #define pq_big(T) priority_queue,less> #define pq_small(T) priority_queue,greater> #define all(a) a.begin(),a.end() #define rep(i,start,end) for(ll i=start;i<(ll)(end);i++) #define per(i,start,end) for(ll i=start;i>=(ll)(end);i--) #define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end()) random_device seed; mt19937_64 randint(seed()); ll grr(ll mi, ll ma) { // [mi, ma) return mi + randint() % (ma - mi); } using mint = modint998244353; using fps = vector; const int MAX=510000; const long long MOD=998244353; long long fac[MAX],finv[MAX],inv[MAX]; void COMinit(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i=0); fps res(1); res[0]=1/f[0]; for(int m=1;m div_fps(fps &f,fps g){ while(!g.empty()&&g.back().val()==0){ g.pop_back(); } if(g.empty()){ cerr<<"ERROR : g is 0"< multipoint_evalution(fps &f,vector &x){ int m=x.size(); int d=0; while((1< tree1(2*n),tree2(2*n); rep(i,0,n){ if(i res; rep(i,0,m){ if(tree2[n+i].size()==0){ res.emplace_back(0); } else{ res.emplace_back(tree2[n+i][0].val()); } } return res; } // sum i = [l, r) : nCi x^i (1 - x)^(n - i) fps sub(int n,int l,int r){ // prod i = [l, r) : 1/i auto finv_rng = [&](int left,int right){ if(left>=right)return (mint)1; mint res=finv[right-1]; res*=fac[left-1]; return res; }; // sum i = [0, lim) : x^i/((ofset_l + 1) * ... * (ofset_l + i)) (1 - x)^(lim - 1 - i) / ((ofset_r + 1) * ... + (ofset_r + lim - 1 - i)) auto work = [&](auto& work,int lim,int ofset_l,int ofset_r){ fps res; if(lim==0){ res={0}; return res; } if(lim==1){ res={1}; return res; } int mid=lim/2; int rem=lim-mid; fps f1=work(work,mid,ofset_l,ofset_r+rem); fps f2=work(work,rem,ofset_l+mid,ofset_r); // f1 * (1 - x)^rem / fac_rng(ofset_r + 1, ofset_r + rem + 1) // f2 * x^mid / fac_rng(ofset_l + 1, ofset_l + mid + 1) fps tag1(rem+1); rep(i,0,rem+1){ tag1[i]=COM(rem,i); if(i%2==1)tag1[i]*=-1; } f1=convolution(f1,tag1); reverse(all(f2)); rep(i,0,mid)f2.emplace_back(0); reverse(all(f2)); mint fac1=finv_rng(ofset_r+1,ofset_r+rem+1),fac2=finv_rng(ofset_l+1,ofset_l+mid+1); for(mint &v1:f1)v1*=fac1; for(mint &v2:f2)v2*=fac2; rep(i,0,max(f1.size(),f2.size())){ res.emplace_back(0); if(i>n>>s>>m; vector ps; rep(i,1,s+1){ mint prob=fac[s]*fac[n+s-i-1]; prob*=finv[s-i]*finv[n+s-1]; ps.emplace_back(prob); } vector a(m+1,0); rep(i,(m+1)/2,m+1){ a[i]=COM(m,i); if((m-i)%2==1)a[i]*=-1; } fps f=sub(m,(m+1)/2,m+1); vector evals=multipoint_evalution(f,ps); mint ans=0; for(mint e:evals){ ans+=e; } ans*=n; cout<