// 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; // fg = 1 mod x^d となるgを求める // https://judge.yosupo.jp/submission/33016 fps inv_fps(fps &f,int d){ int n=f.size(); assert(n!=0&&f[0]!=0); assert(d>=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; } // f(x) の係数が与えられて f(x+c) を x の多項式として展開する // https://judge.yosupo.jp/submission/283667 fps taylor_shift(fps &f,ll c){ if(c==0)return f; int n=f.size(); vector fact(n), rfact(n); fact[0]=1; rfact[0]=1; rep(i,1,n){ fact[i]=fact[i-1]*i; } rfact[n-1]=mint(1)/fact[n-1]; per(i,n-1,2){ rfact[i-1]=rfact[i]*i; } fps f2=f; rep(i,0,n)f2[i]*=fact[i]; reverse(all(f2)); fps expcx(n,1); rep(i,1,n){ expcx[i]=expcx[i-1]*c*rfact[i]*fact[i-1]; } f2=convolution(f2,expcx); while(f2.size()>n)f2.pop_back(); reverse(all(f2)); rep(i,0,n){ f2[i]*=rfact[i]; } return f2; } 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=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 &a,mint p,mint q){ fps f(n+1); mint c=1; rep(i,0,n+1){ f[i]=c*a[i]; c*=p-q; } f=taylor_shift(f,((mint)1/(p-q)).val()); reverse(all(f)); f=taylor_shift(f,q.val()); return f; } fps nv2(int n,vector &a,mint p,mint q){ fps f(n+1,0); fps x1={p-q,1}; fps g={1}; rep(i,0,n+1){ rep(j,0,i+1){ f[n-i+j]+=a[i]*g[j]; } g=convolution(g,x1); } f=taylor_shift(f,q.val()); return f; } fps nv(int n,int l,int r){ fps res(n+1,0); rep(i,l,r){ fps nw(n-i+1); rep(j,0,n-i+1){ nw[j]=COM(n-i,j); if(j%2==1)nw[j]*=-1; } reverse(all(nw)); rep(j,0,i)nw.emplace_back(0); reverse(all(nw)); rep(j,0,n+1){ res[j]+=nw[j]*COM(n,i); } } return res; } void check(){ int n,l,r;cin>>n>>l>>r; fps f=sub(n,l,r); for(mint v:f)cerr< a(n+1,0); rep(i,l,r){ a[i]=COM(n,i); if((n-i)%2==1)a[i]*=-1; } rep(i,0,n+1){ cout<>t; // while(t--)check(); int n,s,m;cin>>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=sub2(m,a,0,-1); // fps f2=sub(m,(m+1)/2,m+1); // for(mint vf:f)cout< evals=multipoint_evalution(f,ps); mint ans=0; for(mint e:evals){ ans+=e; } ans*=n; cout<