#include #include #include #include #include #include #include #include using mint=atcoder::modint998244353; using namespace std; using ll=long long; struct Combination{ int n; vector _fact,_factinv; Combination(int n):n(n){ _fact.resize(n+1,1);_factinv.resize(n+1,1); for(int i=0;i=0;i--)_factinv[i]=_factinv[i+1]*(i+1); } mint fact(int x){ return _fact[x]; } mint factinv(int x){ return _factinv[x]; } mint C(int x,int y){ assert(0<=x&&x<=n&&0<=y); if(x>n>>m; map mpa,mpb; ll n_a=0,n_b=0; Combination comb(3000000); set primes; for(int i=0;i>p>>alpha; n_a+=alpha; mpa[p]=alpha; primes.insert(p); } for(int i=0;i>q>>beta; n_b+=beta; mpb[q]=beta; primes.insert(q); } using P=pair,vector>; auto comp=[](const P& x,const P& y)->bool{ return x.first.size()>y.first.size(); }; priority_queue,decltype(comp)> pq(comp); for(ll p:primes){ ll m_a=mpa[p]; ll m_b=mpb[p]; ll m=min(m_a,m_b); vector fp(m+1),hp(m+1); mint powp=1; for(int i=0;i<=m;i++){ fp[i]=powp*comb.factinv(i)*comb.factinv(m_a-i)*comb.factinv(m_b-i); if(i1){ auto[f1,h1]=pq.top(); pq.pop(); auto[f2,h2]=pq.top(); pq.pop(); auto ff=atcoder::convolution(f1,f2); auto hf=atcoder::convolution(h1,f2); auto fh=atcoder::convolution(f1,h2); int sz=hf.size(); vector h(sz); for(int i=0;i