#include #include using namespace std; using mint=atcoder::modint998244353; template struct combination { combination(int n=0):inner_fac(1,1),inner_finv(1,1){init(n);} mint fac(int n) { init(n); return inner_fac[n]; } mint finv(int n) { init(n); return inner_finv[n]; } mint inv(int n) { if(n==0)return 0; init(n); return inner_fac[n-1]*inner_finv[n]; } mint C(int n, int r) { if(r<0)return 0; if(n<0) { n=-n; mint res=C(n-1+r,r); if(r&1)res=-res; return res; } if(ninner_fac,inner_finv; void init(int n) { int sz=inner_fac.size(); if(sz>n)return; n=min(max(n,2*sz),bound); inner_fac.resize(n+1); inner_finv.resize(n+1); for(int i=sz;i<=n;i++)inner_fac[i]=inner_fac[i-1]*i; inner_finv[n]=inner_fac[n].inv(); for(int i=n;i>sz;i--)inner_finv[i-1]=inner_finv[i]*i; } }; combinationC; vectormultipoint_binomial_sum(const vector>& qs) { auto binom=[&](int n, int k){return C.C(n,k);}; int n_max=2,q=qs.size(); for(auto p:qs)n_max=max(n_max,p.first); const int b=n_max/min(n_max,(int)sqrt(q)); vectoridx(q); for(int i=0;ikj:kires(q); int n=0,k=0; mint ans=1; const mint inv2=mint(2).inv(); for(int i:idx) { auto[ni,ki]=qs[i]; while(k>ki)ans-=binom(n,k--); while(nni)ans=(ans+binom(--n,k))*inv2; res[i]=ans; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int Q; cin>>Q; vector>qs(Q); for(auto&p:qs) { int n,k; cin>>n>>k; p=make_pair(n-1,k-1); } auto binom=multipoint_binomial_sum(qs); for(int i=0;i