代码

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;

const int maxn=(1<<21)+5;
const int sqrtn=sqrt(maxn)+5;
const int inf=0x3f3f3f3f;

namespace poly {
//	/*
	const int mod=998244353;
	const int g=3;
	struct mint {
		int val;
		mint():val(0) {}
		mint(ll tval) {
			if(-mod<=tval&&tval<2*mod) {
				if(tval>=mod) {
					tval-=mod;
				} 
				if(tval<0) {
					tval+=mod;
				}
			} else {
				tval%=mod;
				if(tval<0) {
					tval+=mod;
				}			
			}
			val=tval;
		}
		mint& operator += (const mint &b) {
			val=val+b.val>=mod?val+b.val-mod:val+b.val;
			return *this;
		}
		mint& operator -= (const mint &b) {
			val=val-b.val<0?val-b.val+mod:val-b.val;
			return *this;
		}
		mint& operator *= (const mint &b) {
			val=1ll*val*b.val>=mod?1ll*val*b.val%mod:val*b.val;
			return *this;
		}
		mint& operator /= (const mint &b) {
			*this*=b.inv();
			return *this;
		}
		friend mint operator + (const mint &a,const mint &b) {
			mint ans=a;
			ans+=b;
			return ans;
		}
		friend mint operator - (const mint &a,const mint &b) {
			mint ans=a;
			ans-=b;
			return ans;
		}
		friend mint operator * (const mint &a,const mint &b) {
			mint ans=a;
			ans*=b;
			return ans;
		}
		friend mint operator / (const mint &a,const mint &b) {
			mint ans=a;
			ans/=b;
			return ans;
		}
		friend bool operator < (const mint &a,const mint &b) {
			return a.val<b.val;
		}
		friend bool operator > (const mint &a,const mint &b) {
			return a.val>b.val;
		}
		friend bool operator == (const mint &a,const mint &b) {
			return a.val==b.val;
		}
		friend bool operator != (const mint &a,const mint &b) {
			return a.val!=b.val;
		}
		friend istream& operator >> (istream &is,mint &x) {
			ll val;
			cin>>val;
			x.val=val%mod; 
			return is;
		}
		friend ostream& operator << (ostream &os,const mint &x) {
			os<<x.val;
			return os;
		}
		mint qpow(ll y) const {
			mint x=*this,ans=1;
			while(y) {
				if(y&1) {
					ans*=x;
				} 
				x*=x;
				y>>=1;
			}
			return ans;
		}
		mint inv() const {
			// mod must be a prime
			return qpow(mod-2);
		}
		mint sqrt() {
			mint a=*this; 
			auto check=[&](mint x) {
				return x.qpow((mod-1)/2)==1;
			};
			static mt19937 rnd(73385);
			mint b=rnd()%mod;
			while(check(b*b-a)) {
				b=rnd()%mod;
			}
			static mint val=b*b-a;
			struct Complex {
				mint real,imag;
				Complex(mint treal=0,mint timag=0):real(treal),imag(timag) {}
				Complex operator * (const Complex &rhs) {
					return {real*rhs.real+imag*rhs.imag*val,real*rhs.imag+imag*rhs.real};
				}
				Complex& operator *= (const Complex &rhs) {
					return *this=*this*rhs;
				}
			};
			auto qpow=[&](Complex x,int y) {
				Complex ans={1};
				while(y) {
					if(y&1) {
						ans*=x;
					}
					x*=x;
					y>>=1;
				}
				return ans;
			};
			mint ans=qpow({b,1},(mod+1)/2).real;
			return min(ans,mod-ans);
		}
	};
	struct Pow {
		const int B=4e4;
		mint p1[maxn];
		mint p2[maxn];
		mint pow(int y) {
			return p1[y%B]*p2[y/B];
		}
		void prepare(mint p) {
			p1[0]=1;
			for(int i=1;i<=B;i++) {
				p1[i]=p*p1[i-1];
		 	}
			mint ans=1;
			for(int i=1;i<=B;i++) {
				ans*=p;
			}
			p2[0]=1,p2[1]=ans;
			for(int i=2;i<=B;i++) {
				p2[i]=p2[i-1]*ans;
			}
		}
	} pw;
	using Poly=vector<mint>;
	int t[maxn];
	bool inited=false;
	Poly s[sqrtn];
	Poly l[sqrtn];
	mint w[maxn][2];
	mint fact[maxn];
	mint invf[maxn];
	map<pii,Poly> mp;
	void init() {
		inited=true;
		for(int i=1;i<maxn;i*=2) {
			w[i][0]=mint(g).qpow((mod-1)/i);
			w[i][1]=w[i][0].inv();
		}
	} 
	int extend(int x) {
		int len=1;
		while(len<x) {
			len*=2;
		}
		return len;
	}
	void NTT(Poly &f,int op) {
		int len=f.size();
		for(int i=0;i<len;i++) {
			t[i]=t[i>>1]>>1;
			if(i&1) {
				t[i]|=len>>1;
			}
		}
		for(int i=0;i<len;i++) {
			if(t[i]<i) {
				swap(f[t[i]],f[i]);
			}
		}
		for(int n=2;n<=len;n*=2) {
			mint p=w[n][op];
			for(int dt=0;dt<len;dt+=n) {
				mint cur=1;
				for(int i=0;i<n/2;i++) {
					mint t=cur*f[i+n/2+dt];
					f[i+n/2+dt]=f[i+dt]-t;
					f[i+dt]=f[i+dt]+t;
					cur*=p;
				}
			}
		}
	}
	void DFT(Poly &f) {
		NTT(f,0);
	}
	void IDFT(Poly &f) {
		NTT(f,1);
		int len=f.size();
		mint invlen=mint(len).inv();
		for(mint &x:f) {
			x*=invlen;
		}
	}
	Poly mul(Poly a,Poly b,int p=-1) {
		assert(inited);
		int n=a.size(),m=b.size(),len=extend(n+m-1);
		if(p==-1) {
			p=n+m-1;
		}
		if(n<=100||m<=100) {
			Poly ans(n+m-1);
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					ans[i+j]+=a[i]*b[j];
				}
			}
			ans.resize(p);
			return ans;
		}
		a.resize(len);
		b.resize(len);
		DFT(a),DFT(b);
		for(int i=0;i<len;i++) {
			a[i]*=b[i];
		}
		IDFT(a);
		a.resize(p);
		return a;
	}
//	*/ 
	/*
	int mod;
	const double pi=acos(-1);
	struct mint {
		static int mod;
		int val;
		mint():val(0) {}
		mint(ll tval) {
			assert(mod);
			if(-mod<=tval&&tval<2*mod) {
				if(tval>=mod) {
					tval-=mod;
				} 
				if(tval<0) {
					tval+=mod;
				}
			} else {
				tval%=mod;
				if(tval<0) {
					tval+=mod;
				}			
			}
			val=tval;
		}
		mint& operator += (const mint &b) {
			val=val+b.val>=mod?val+b.val-mod:val+b.val;
			return *this;
		}
		mint& operator -= (const mint &b) {
			val=val-b.val<0?val-b.val+mod:val-b.val;
			return *this;
		}
		mint& operator *= (const mint &b) {
			val=1ll*val*b.val>=mod?1ll*val*b.val%mod:val*b.val;
			return *this;
		}
		mint& operator /= (const mint &b) {
			*this*=b.inv();
			return *this;
		}
		friend mint operator + (const mint &a,const mint &b) {
			mint ans=a;
			ans+=b;
			return ans;
		}
		friend mint operator - (const mint &a,const mint &b) {
			mint ans=a;
			ans-=b;
			return ans;
		}
		friend mint operator * (const mint &a,const mint &b) {
			mint ans=a;
			ans*=b;
			return ans;
		}
		friend mint operator / (const mint &a,const mint &b) {
			mint ans=a;
			ans/=b;
			return ans;
		}
		friend bool operator < (const mint &a,const mint &b) {
			return a.val<b.val;
		}
		friend bool operator > (const mint &a,const mint &b) {
			return a.val>b.val;
		}
		friend bool operator == (const mint &a,const mint &b) {
			return a.val==b.val;
		}
		friend bool operator != (const mint &a,const mint &b) {
			return a.val!=b.val;
		}
		friend istream& operator >> (istream &is,mint &x) {
			ll val;
			cin>>val;
			x.val=val%mod; 
			return is;
		}
		friend ostream& operator << (ostream &os,const mint &x) {
			os<<x.val;
			return os;
		}
		mint qpow(ll y) const {
			mint x=*this,ans=1;
			while(y) {
				if(y&1) {
					ans*=x;
				} 
				x*=x;
				y>>=1;
			}
			return ans;
		}
		mint inv() const {
			// mod must be a prime
			return qpow(mod-2);
		}
		mint sqrt() {
			mint a=*this; 
			auto check=[&](mint x) {
				return x.qpow((mod-1)/2)==1;
			};
			static mt19937 rnd(73385);
			mint b=rnd()%mod;
			while(check(b*b-a)) {
				b=rnd()%mod;
			}
			static mint val=b*b-a;
			struct Complex {
				mint real,imag;
				Complex(mint treal=0,mint timag=0):real(treal),imag(timag) {}
				Complex operator * (const Complex &rhs) {
					return {real*rhs.real+imag*rhs.imag*val,real*rhs.imag+imag*rhs.real};
				}
				Complex& operator *= (const Complex &rhs) {
					return *this=*this*rhs;
				}
			};
			auto qpow=[&](Complex x,int y) {
				Complex ans={1};
				while(y) {
					if(y&1) {
						ans*=x;
					}
					x*=x;
					y>>=1;
				}
				return ans;
			};
			mint ans=qpow({b,1},(mod+1)/2).real;
			return min(ans,mod-ans);
		}
	};
	struct Pow {
		const int B=4e4;
		mint p1[maxn];
		mint p2[maxn];
		mint pow(int y) {
			return p1[y%B]*p2[y/B];
		}
		void prepare(mint p) {
			p1[0]=1;
			for(int i=1;i<=B;i++) {
				p1[i]=p*p1[i-1];
		 	}
			mint ans=1;
			for(int i=1;i<=B;i++) {
				ans*=p;
			}
			p2[0]=1,p2[1]=ans;
			for(int i=2;i<=B;i++) {
				p2[i]=p2[i-1]*ans;
			}
		}
	} pw;
	using Complex=complex<double>;
	using Poly=vector<mint>;
	int t[maxn];
	int mint::mod;
	bool inited=false;
	Poly s[sqrtn];
	Poly l[sqrtn];
	mint fact[maxn];
	mint invf[maxn];
	map<pii,Poly> mp;
	void init(int p) {
		mod=p;
		mint::mod=p;
		inited=true;
	} 
	int extend(int x) {
		int len=1;
		while(len<x) {
			len*=2;
		}
		return len;
	}
	void FFT(vector<Complex> &f,int op) {
		int len=f.size();
		for(int i=0;i<len;i++) {
			t[i]=t[i>>1]>>1;
			if(i&1) {
				t[i]|=len>>1;
			}
		}
		for(int i=0;i<len;i++) {
			if(t[i]<i) {
				swap(f[t[i]],f[i]);
			}
		}
		for(int n=2;n<=len;n*=2) {
			vector<Complex> ws(n/2);
			for(int i=0;i<n/2;i++) {
				ws[i]={cos(2*pi*i/n),sin(2*pi*i/n)*(!op?1:-1)};
			}
			for(int dt=0;dt<len;dt+=n) {
				for(int i=0;i<n/2;i++) {
					Complex t=ws[i]*f[i+n/2+dt];
					f[i+n/2+dt]=f[i+dt]-t;
					f[i+dt]=f[i+dt]+t;
				}
			}
		}
	}
	void DFT(vector<Complex> &f) {
		FFT(f,0);
	}
	void DFT(vector<Complex> &a,vector<Complex> &b) {
		int len=a.size();
		for(int i=0;i<len;i++) {
			a[i].imag(b[i].real());
		}
		DFT(a);
		b[0]=conj(a[0]);
		for(int i=1;i<len;i++) {
			b[i]=conj(a[len-i]);
		}
		for(int i=0;i<len;i++) {
			Complex x=a[i],y=b[i];
			a[i]=(x+y)/(Complex){2,0};
			b[i]=(x-y)/(Complex){0,2};
		}
	}
	void IDFT(vector<Complex> &f) {
		FFT(f,1);
		int len=f.size();
		for(Complex &x:f) {
			x/=len;
		}
	}
	void IDFT(vector<Complex> &a,vector<Complex> &b) {
		int len=a.size();
		for(int i=0;i<len;i++) {
			a[i]+=b[i]*(Complex){0,1};
		}
		IDFT(a);
		for(int i=0;i<len;i++) {
			b[i]=a[i].imag();
			a[i].imag(0);
		}
	}
	Poly mul(Poly ta,Poly tb,int p=-1) {
		int n=ta.size(),m=tb.size(),len=extend(n+m-1);
		if(p==-1) {
			p=n+m-1;
		}
		if(n<=200||m<=200) {
			Poly ans(n+m-1);
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					ans[i+j]+=ta[i]*tb[j];
				}
			}
			ans.resize(p);
			return ans;
		}
		vector<Complex> a,b,c,d;
		int L=1<<15;
		for(mint x:ta) {
			a.push_back(x.val/L);
			b.push_back(x.val%L);
		}
		for(mint x:tb) {
			c.push_back(x.val/L);
			d.push_back(x.val%L);
		}
		a.resize(len);
		b.resize(len);
		c.resize(len);
		d.resize(len);
		DFT(a,b),DFT(c,d);
		for(int i=0;i<len;i++) {
			Complex A=a[i],B=b[i],C=c[i],D=d[i];
			a[i]=A*C;
			b[i]=A*D+B*C;
			c[i]=B*D;
		}
		IDFT(a,b),IDFT(c);
		Poly ans(len);
		auto get=[&](vector<Complex> &f,int i) -> int {
			return (ll)(round(f[i].real()))%mint::mod;	
		};
		for(int i=0;i<len;i++) {
			ans[i]=(1ll*get(a,i)*L%mint::mod*L%mint::mod+1ll*get(b,i)*L%mint::mod+get(c,i))%mint::mod;
		}
		ans.resize(p); 
		return ans;
	}
	*/
	void plus(Poly &a,Poly b) {
		int n=a.size(),m=b.size();
		a.resize(max(n,m));
		for(int i=0;i<m;i++) {
			a[i]+=b[i];
		}
	}
	void sub(Poly &a,Poly b) {
		int n=a.size(),m=b.size();
		a.resize(max(n,m));
		for(int i=0;i<m;i++) {
			a[i]-=b[i];
		}
	}
	Poly split(Poly &a,int n) {
		Poly b;
		for(int i=0;i<n&&i<a.size();i++) {
			b.push_back(a[i]);
		}
		return b;
	}
	Poly inv(Poly a,int n=-1) {
		assert(a[0].val);
		if(n==-1) {
			n=a.size();
		}
		Poly ans(1);
		ans[0]=a[0].inv();
		int len=1;
		while(len<n) {
			len*=2;
			Poly t=ans;
			for(mint &x:ans) {
				x*=2;
			}	
			sub(ans,mul(mul(t,t,len),split(a,len),len));
			ans.resize(len);
		}
		ans.resize(n);
		return ans;
	}
	Poly sqrt(Poly a,int n=-1) {
		if(n==-1) {
			n=a.size();
		}
		Poly ans(1);
		ans[0]=a[0].sqrt();
		int len=1;
		while(len<n) {
			len*=2;
			Poly t=ans;
			for(mint &x:t) {
				x*=2;
			}
			ans=mul(ans,ans,len);
			plus(ans,split(a,len));
			ans=mul(ans,inv(t,len),len);
			ans.resize(len);
		}
		ans.resize(n);
		return ans;
	}
	Poly diff(Poly a) {
		Poly ans(a.size()-1);
		for(int i=0;i+1<a.size();i++) {
			ans[i]=a[i+1]*(i+1);
		}
		return ans;
	}
	void pfact(int n) {
		fact[0]=invf[0]=1;
		for(int i=1;i<=n;i++) {
			fact[i]=fact[i-1]*i;
		}
		invf[n]=fact[n].inv();
		for(int i=n-1;i>=1;i--) {
			invf[i]=invf[i+1]*(i+1);
		}
	}
	Poly inte(Poly a) {
		Poly ans(a.size()+1);
		pfact(a.size()); 
		for(int i=0;i<a.size();i++) {
			ans[i+1]=a[i]*invf[i+1]*fact[i];
		}
		return ans;
	}
	Poly ln(Poly a,int n=-1) {
		assert(a[0]==1);
		if(n==-1) {
			n=a.size();
		}
		return inte(mul(diff(a),inv(a,n),n-1));
	} 
	Poly exp(Poly a,int n=-1) {
		assert(!a[0].val);
		if(n==-1) {
			n=a.size();
		}
		Poly ans(1);
		ans[0]=1;
		int len=1;
		while(len<n) {
			len*=2;
			Poly t=ln(ans,len);
			for(mint &x:t) {
				x=0-x;
			}
			plus(t,split(a,len));
			t[0]+=1;
			ans=mul(ans,t);
			ans.resize(len);
		}
		ans.resize(n);
		return ans;
	}
	Poly merge(Poly a,Poly b) {
		// return : length = n
		int n=a.size(),B=std::sqrt(n)*2;
		s[0].resize(n),s[0][0]=1;
		s[1]=b,s[1].resize(n);
		for(int i=2;i<B;i++) {
			s[i]=mul(s[i-1],b,n);
		}
		l[0].resize(n),l[0][0]=1;
		l[1]=mul(b,s[B-1],n);
		for(int i=2;i<=n/B;i++) {
			l[i]=mul(l[i-1],l[1],n);
		}
		Poly ans(n);
		for(int i=0;i<=n/B;i++) {
			Poly t(n);
			for(int j=0;j<B&&i*B+j<n;j++) {
				mint x=a[i*B+j];
				int k=0;
				for(;k+3<n;k+=4) {
					t[k]+=x*s[j][k];
					t[k+1]+=x*s[j][k+1];
					t[k+2]+=x*s[j][k+2];
					t[k+3]+=x*s[j][k+3];
				}
				for(;k<n;k++) {
					t[k]+=x*s[j][k];
				}
			}
			plus(ans,mul(t,l[i],n));
		}
		return ans;
	}
	Poly pow(Poly a,int k,int n=-1) {
		// a[0] = 1 must hold
		if(n==-1) {
			n=a.size();
		}
		a=ln(a);
		for(mint &x:a) {
			x*=k;
		}
		return exp(a);
	} 
	Poly pow(Poly a,int m1,int m2,double m3,int n=-1) {
		// m1: mod p
		// m2: mod phi(p)
		// m3: real p
		if(n==-1) {
			n=a.size();
		}
		int mv;
		bool f=false;
		mint p;
		for(int i=0;i<a.size();i++) {
			if(a[i].val) {
				f=true;
				if(i*m3>=n) {
					Poly e(n);
					return e;
				}
				mv=(int)(m3)*i;
				p=a[i];
				mint inv=a[i].inv(); 
				for(mint &x:a) {
					x*=inv;
				} 
				for(int j=0;j+i<a.size();j++) {
					a[j]=a[j+i];
				}
				for(int j=1;j<=i;j++) {
					a.pop_back();
				} 
				for(int j=1;j<=i;j++) {
					a.push_back(0);
				}
				break;
			}
		}
		if(!f) {
			return a;
		}
		a=ln(a);
		for(mint &x:a) {
			x*=m1;
		}
		a=exp(a);
		for(mint &x:a) {
			x*=p.qpow(m2);
		}
		for(int i=a.size();i>=mv;i--) {
			a[i]=a[i-mv];
		}
		for(int i=0;i<mv;i++) {
			a[i]=0;
		}
		return a;
	}
	Poly sum(Poly a,int k,int n=-1) {
		if(n==-1) {
			n=a.size();
		}
		Poly b(n);
		b[0]=1;
		pfact(n);
		for(int i=1;i<n;i++) {
			b[i]=1ll*b[i-1]*(k+i-1)*fact[i-1]*invf[i];
		}
		return mul(a,b,n);
	}
	Poly diff(Poly a,int k,int n=-1) {
		if(n==-1) {
			n=a.size();
		}
		Poly b(n);
		b[0]=1;
		pfact(n);
		for(int i=1;i<n;i++) {
			b[i]=1ll*b[i-1]*(k-i+1)*fact[i-1]*invf[i]*(-1);
		}
		return mul(a,b,n);
	}
	Poly rev(Poly a) {
		reverse(a.begin(),a.end());
		return a;
	}
	pair<Poly,Poly> div(Poly a,Poly b) {
		int n=a.size(),m=b.size();
		a=rev(a),b=rev(b);
		Poly c=mul(a,inv(b,n-m+1),n-m+1);
		c=rev(c);
		a=rev(a);
		sub(a,mul(rev(b),c));
		a.resize(m-1);
		return {c,a};
	}
	Poly getv(Poly a,Poly b) {
		function<void(int,int)> build=[&](int l,int r) {
			if(l==r) {
				mp[{l,r}]={0-b[l],1};
				return ;
			}
			int mid=(l+r)>>1;
			build(l,mid);
			build(mid+1,r);
			mp[{l,r}]=mul(mp[{l,mid}],mp[{mid+1,r}]);
		};
		int m=b.size();
		build(0,m-1);
		Poly ans(m);
		function<void(Poly,int,int)> solve=[&](Poly f,int l,int r) {
			if(l==r) {
				ans[l]=f[0];
				return ;
			}	
			int mid=(l+r)>>1;
			solve(div(f,mp[{l,mid}]).sec,l,mid);
			solve(div(f,mp[{mid+1,r}]).sec,mid+1,r);
		};
		solve(a,0,m-1);
		return ans;
	}
	Poly getf(Poly x,Poly y) {
		function<Poly(int,int)> calc=[&](int l,int r) -> Poly {
			if(l==r) {
				return {0-x[l],1};
			}
			int mid=(l+r)>>1;
			return mul(calc(l,mid),calc(mid+1,r));
		};
		int n=x.size();
		Poly m=calc(0,n-1);
		m=diff(m);
		Poly v=getv(m,x);
		for(int i=0;i<n;i++) {
			v[i]=y[i]/v[i];
		}
		function<pair<Poly,Poly>(int,int)> solve=[&](int l,int r) -> pair<Poly,Poly> {
			if(l==r) {
				return {{0-x[l],1},{v[l]}};	
			}
			int mid=(l+r)>>1;
			auto al=solve(l,mid),ar=solve(mid+1,r);
			Poly ml=al.fir,fl=al.sec,mr=ar.fir,fr=ar.sec,t=mul(fl,mr);
			plus(t,mul(fr,ml));
			return {mul(ml,mr),t};
		};
		return solve(0,n-1).sec;
	}
	Poly sin(Poly a) {
		mint i=mint(-1).sqrt();
		for(mint &x:a) {
			x*=i;
		}
		Poly ans=exp(a);
		for(mint &x:a) {
			x*=-1;
		}
		sub(ans,exp(a));
		mint inv=mint(2).inv()*i.inv();
		for(mint &x:ans) {
			x*=inv;
		}
		return ans;
	}
	Poly cos(Poly a) {
		mint i=mint(-1).sqrt();
		for(mint &x:a) {
			x*=i;
		}
		Poly ans=exp(a);
		for(mint &x:a) {
			x*=-1;
		}
		plus(ans,exp(a));
		mint inv=mint(2).inv();
		for(mint &x:ans) {
			x*=inv;
		}
		return ans;
	} 
	Poly asin(Poly a) {
		int n=a.size();
		Poly t=diff(a);
		a=mul(a,a,n-1);
		for(mint &x:a) {
			x=0-x;
		}
		a[0]+=1;
		return inte(mul(t,inv(sqrt(a,n-1),n-1),n-1));
	}
	Poly atan(Poly a) {
		int n=a.size();
		Poly t=diff(a);
		a=mul(a,a,n-1);
		a[0]+=1;
		return inte(mul(t,inv(a,n-1),n-1));
	}
	Poly Z(Poly a,mint c,int m=-1) {
		if(m==-1) {
			m=a.size();
		}
		// a(c^0), a(c^1), ..., a(c^{m-1})
		int n=a.size();
		Poly t(n+m);
		vector<int> C(n+m);
		pw.prepare(c);
		for(int i=0;i<=n+m-1;i++) {
			C[i]=1ll*i*(i-1)/2%(mod-1);
			t[i]=pw.pow(C[i]);
		}
		for(int i=0;i<n;i++) {
			a[i]*=pw.pow((-C[i]+mod-1)%(mod-1));
		}
		a=mul(a,rev(t));
		Poly ans;
		for(int i=m+n-1;i>=n;i--) {
			ans.push_back(a[i]);
		}
		for(int i=0;i<m;i++) {
			ans[i]*=pw.pow((-C[i]+mod-1)%(mod-1));
		}
		return ans;
	}
	Poly omultiset(Poly a,int m) {
		pfact(m);
		auto inv=[&](int x) {
			return fact[x-1]*invf[x];	
		};
		Poly b(m+1);
		for(int i=1;i<a.size();i++) {
			for(int n=1;i*n<=m;n++) {
				b[i*n]+=a[i]*inv(n);
			}
		}
		Poly ans=exp(b);
		ans.resize(m+1);
		return ans;
	}
	istream& operator >> (istream &is,Poly &f) {
		for(mint &x:f) {
			is>>x;
		}
		return is;
	}
	ostream& operator << (ostream &os,Poly f) {
		for(int i=0;i<f.size();i++) {
			os<<f[i];
			if(i!=f.size()-1) {
				os<<" ";
			}
		}
		return os;
	}
}
using namespace poly;

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
	Poly ta,tb;
	for(int i=0;i<=n;i++) {
		ta.push_back(a[i]);
	}	
	for(int i=0;i<=m;i++) {
		tb.push_back(b[i]);
	}
	ta=mul(ta,tb);
	for(int i=0;i<=n+m;i++) {
		c[i]=ta[i].val;
	}
}

评测结果