QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#700390#9493. 路径计数TheZone100 ✓8696ms406256kbC++2341.0kb2024-11-02 12:54:022024-11-02 12:54:02

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 12:54:02]
  • 评测
  • 测评结果：100
  • 用时：8696ms
  • 内存：406256kb
查看
  • [2024-11-02 12:54:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
int sid;
using poly=vector<int>;
using vec=array<poly,2>;
using matrix=array<vec,2>;
#ifdef DEBUG
ostream& operator << (ostream &out,vec a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
ostream& operator << (ostream &out,matrix a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
#endif
namespace sub10{
	int mod=998244353,base;
	using comp=complex<double>;
	struct fastmod {
	typedef unsigned long long u64;
	typedef __uint128_t u128;

	int m;
	u64 b;

	fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
	int reduce(u64 a) {
		u64 q = ((u128)a * b) >> 64;
		int r = a - q * m;
		return r < m ? r : r - m;
	}
	} Fast(2);
	namespace Poly{
		const double pi=acos(-1);
		const int N=1<<20;
		int lim,rev[N];
		comp a0[N],a1[N],b0[N],b1[N],c0[N],c1[N],c2[N],pw[N];
		void Init(){
			for(int len=1;len<N;len<<=1){
				for(int i=0;i<len;i++){
					pw[len|i]=comp(cos(pi/len*i),sin(pi/len*i));
				}
			}
		}
		void init(int n){
			for(lim=1;lim<n;lim<<=1);
			for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
		}
		namespace Public{
			void FFT(comp *a,int op){
				for(int i=0;i<lim;i++)if(rev[i]<i)swap(a[rev[i]],a[i]);
				for(int len=1;len<lim;len<<=1){
					for(int i=0;i<lim;i+=len<<1){
						for(int j=0;j<len;j++){
							comp x=a[i|j],y=a[i|j|len]*pw[len|j];
							a[i|j]=x+y,a[i|j|len]=x-y;
						}
					}
				}
				if(op<0){
					reverse(a+1,a+lim);
					for(int i=0;i<lim;i++)a[i]/=lim;
				}
			}
			void DFT(const poly &a,comp *a0,comp *a1){
				int n=a.size();
				for(int i=0;i<n;i++)a0[i]=comp(a[i]%base,a[i]/base);
				fill(a0+n,a0+lim,comp(0,0));
				FFT(a0,1);
				copy(a0,a0+lim,a1);
				reverse(a1+1,a1+lim);
				for(int i=0;i<lim;i++)a1[i]=conj(a1[i]);
				for(int i=0;i<lim;i++){
					comp p=a0[i],q=a1[i];
					a0[i]=(p+q)*comp(0.5,0);
					a1[i]=(q-p)*comp(0,0.5);
				}
			}
			poly iDFT(comp *c0,comp *c1){
				FFT(c0,-1),FFT(c1,-1);
				auto calc=[&](double x)->ll {
					if(x>0)return Fast.reduce(ll(x+0.5));
					else{
						int res=Fast.reduce(-ll(x-0.5));
						return res?mod-res:0;
					}
				};
				poly c(lim);
				for(int i=0;i<lim;i++){
					c[i]=Fast.reduce(calc(imag(c1[i]))*base*base+calc(real(c0[i]))*base+calc(real(c1[i])));
				}
				return c;
			}
			pair<poly,poly> iDFT(comp *c0,comp *c1,comp *d0,comp *d1){
				for(int i=0;i<lim;i++)c0[i]+=comp(0,1)*d0[i];
				FFT(c0,-1),FFT(c1,-1),FFT(d1,-1);
				auto calc=[&](double x)->ll {
					if(x>0)return Fast.reduce(ll(x+0.5));
					else{
						int res=Fast.reduce(-ll(x-0.5));
						return res?mod-res:0;
					}
				};
				poly c(lim),d(lim);
				for(int i=0;i<lim;i++){
					c[i]=Fast.reduce(calc(imag(c1[i]))*base*base+calc(real(c0[i]))*base+calc(real(c1[i])));
				}
				for(int i=0;i<lim;i++){
					d[i]=Fast.reduce(calc(imag(d1[i]))*base*base+calc(imag(c0[i]))*base+calc(real(d1[i])));
				}
				return make_pair(c,d);
			}
			void inc(comp *a0,comp *a1,comp *b0,comp *b1,comp *c0,comp *c1){
				for(int i=0;i<lim;i++){
					c0[i]+=a1[i]*b0[i]+a0[i]*b1[i];
					c1[i]+=a0[i]*b0[i]+comp(0,1)*a1[i]*b1[i];
				}
			}
			poly operator * (const poly &a,const poly &b){
				int n=a.size(),m=b.size(),k=n+m-1;
				if(min(n,m)<=40){
					poly c(k);
					for(int i=0;i<n;i++){
						for(int j=0;j<m;j++){
							c[i+j]=Fast.reduce(c[i+j]+1ll*a[i]*b[j]);
						}
					}
					return c;
				}
				init(k);
				DFT(a,a0,a1),DFT(b,b0,b1);
				fill(c0,c0+lim,comp(0,0));
				fill(c1,c1+lim,comp(0,0));
				inc(a0,a1,b0,b1,c0,c1);
				auto c=iDFT(c0,c1);
				return c.resize(k),c;
			}
			poly& operator *= (poly &a,const poly &b){
				return a=a*b;
			}
			poly& operator += (poly &a,const poly &b){
				int n=a.size(),m=b.size();
				if(n<m)a.resize(m);
				for(int i=0;i<m;i++)(a[i]+=b[i])>=mod&&(a[i]-=mod);
				return a;
			}
			poly operator + (const poly &a,const poly &b){
				poly c(a);
				return c+=b;
			}
			poly& operator -= (poly &a,const poly &b){
				int n=a.size(),m=b.size();
				if(n<m)a.resize(m);
				for(int i=0;i<m;i++)(a[i]-=b[i])<0&&(a[i]+=mod);
				return a;
			}
			poly operator - (const poly &a,const poly &b){
				poly c(a);
				return c-=b;
			}
			poly operator - (const poly &a){
				return poly()-a;
			}
			poly& operator *= (poly &a,const int &b){
				for(int &x:a)x=Fast.reduce(1ll*x*b);
				return a;
			}
			poly operator * (const poly &a,const int &b){
				poly c(a);
				return c*=b;
			}
			poly& operator %= (poly &a,const int &b){
				if(a.size()>b)a.resize(b);
				return a;
			}
			poly operator % (const poly &a,const int &b){
				poly c(a);
				return c%=b;
			}
			poly inv(poly a,int n=-1){
				if(n==-1)n=a.size();
				if(n==1)return poly(1,1);
				int m=(n+1)/2;
				auto b=inv(a%m,m);
				init(n+m-1);
				static comp a0[N],a1[N],b0[N],b1[N],c0[N],c1[N];
				DFT(a,a0,a1),DFT(b,b0,b1);
				fill(c0,c0+lim,comp(0,0));
				fill(c1,c1+lim,comp(0,0));
				inc(a0,a1,b0,b1,c0,c1);
				a=iDFT(c0,c1),a.resize(n);
				DFT(a,a0,a1);
				fill(c0,c0+lim,comp(0,0));
				fill(c1,c1+lim,comp(0,0));
				inc(a0,a1,b0,b1,c0,c1);
				a=iDFT(c0,c1),a.resize(n);
				return b*2-a;
			}
		}
	}
	using namespace Poly::Public;
	const int N=2e5+10,M=1<<19|10;
	int sid,n,m,a[N],b[N],c[N],d[N],e[N],f[N];
	comp buf[20][M];
	matrix operator * (matrix a,matrix b){
		int n=0;
		for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
			n=max(n,(int)a[i][j].size()+(int)b[j][k].size()-1);
		}
		matrix c;
		if(n<=50){
			for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
				if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
			}
			return c;
		}
		Poly::init(n),n=Poly::lim;
		static comp *a0[2][2]={{buf[0],buf[1]},{buf[2],buf[3]}};
		static comp *a1[2][2]={{buf[4],buf[5]},{buf[6],buf[7]}};
		static comp *b0[2][2]={{buf[8],buf[9]},{buf[10],buf[11]}};
		static comp *b1[2][2]={{buf[12],buf[13]},{buf[14],buf[15]}};
		static comp *c0=buf[16],*c1=buf[17];
		for(int i:{0,1})for(int j:{0,1}){
			DFT(a[i][j],a0[i][j],a1[i][j]);
			DFT(b[i][j],b0[i][j],b1[i][j]);
		}
		for(int i:{0,1})for(int j:{0,1}){
			fill(c0,c0+n,comp(0,0));
			fill(c1,c1+n,comp(0,0));
			for(int k:{0,1})inc(a0[i][k],a1[i][k],b0[k][j],b1[k][j],c0,c1);
			c[i][j]=iDFT(c0,c1);
			for(;!c[i][j].empty()&&!c[i][j].back();c[i][j].pop_back());
		}
		return c;
	}
	matrix mul(matrix a,matrix b){
		matrix c;
		for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
			if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
		}
		return c;
	}
	vec solve(int l,int r){
		if(l==r){
			// debug("solve",l,r,vec{poly{b[l],1},poly{e[l]}});
			return vec{poly{b[l],1},poly{e[l]}};
		}
		int mid=(l+r)>>1,n=0;
		auto L=solve(l,mid),R=solve(mid+1,r);
		for(int i:{0,1})for(int j:{0,1})if(!i||!j){
			n=max(n,(int)L[i].size()+(int)R[j].size()-1);
		}
		// debug("solve",l,r);
		Poly::init(n),n=Poly::lim;
		vec t;
		static comp *L0=buf[0],*L1=buf[1];
		static comp *R0[2]={buf[2],buf[3]},*R1[2]={buf[4],buf[5]};
		static comp *t0[2]={buf[6],buf[7]},*t1[2]={buf[8],buf[9]};
		DFT(L[0],L0,L1);
		for(int i:{0,1}){
			fill(t0[i],t0[i]+n,comp(0,0));
			fill(t1[i],t1[i]+n,comp(0,0));
			DFT(R[i],R0[i],R1[i]);
		}
		inc(L0,L1,R0[0],R1[0],t0[0],t1[0]);
		inc(L0,L1,R0[1],R1[1],t0[1],t1[1]);
		tie(t[0],t[1])=iDFT(t0[0],t1[0],t0[1],t1[1]);
		for(int i:{0,1}){
			for(;!t[i].empty()&&!t[i].back();t[i].pop_back());
		}
		t[1]+=L[1];
		// debug("solve",l,r,t);
		return t;
	}
	struct node{
		matrix F;
		poly G[2][3];
		poly calc(int cr){
			return F[0][0]*poly{(mod-cr)%mod,1}+F[0][1];
		}
		void mul(poly g,int k){
			Poly::init(G[0][0].size()+g.size()-1);
			int n=Poly::lim;
			static comp *g0=buf[0],*g1=buf[1],*w0[2]={buf[2],buf[3]},*w1[2]={buf[4],buf[5]};
			static comp *G0=buf[6],*G1=buf[7];
			DFT(g,g0,g1);
			for(int j:{0,1,2}){
				for(int i:{0,1}){
					DFT(G[i][j],G0,G1);
					fill(w0[i],w0[i]+n,comp(0,0));
					fill(w1[i],w1[i]+n,comp(0,0));
					inc(g0,g1,G0,G1,w0[i],w1[i]);
				}
				tie(G[0][j],G[1][j])=iDFT(w0[0],w1[0],w0[1],w1[1]);
				G[0][j].resize(k),G[1][j].resize(k);
			}
		}
	};
	void expand(poly &a,poly f,poly g,int m){
		int n=a.size();
		if(m<=n)return a%=m,void();
		a=a*f%n*g%m;
	}
	const int K=400;
	matrix gen(int i){
		matrix cur;
		cur[0][0]=poly{(mod-c[i])%mod,1};
		cur[0][1]=poly{int(1ll*(mod-a[i])*d[i+1]%mod)};
		cur[1][0]=poly{1};
		return cur;
	}
	node divide(int l,int r){
		int n=r-l+1;
		if(r-l+1<=K){
			node res;
			function<matrix(int,int)>dfs=[&](int l,int r){
				if(l==r)return gen(l);
				int mid=(l+r)>>1;
				return dfs(l,mid)*dfs(mid+1,r);
			};
			if(l<r)res.F=dfs(l,r-1);
			else res.F[0][0]=res.F[1][1]=poly{1};
			static int w[K][N];
			for(int x:{0,1}){
				for(int i=0;i<n;i++)fill(w[i]+l,w[i]+1+r,0);
				w[0][x?r:l]=1;
				for(int i=0;i+1<n;i++){
					for(int j=l;j<=r;j++)w[i+1][j]=Fast.reduce(w[i+1][j]+1ll*w[i][j]*c[j]);
					for(int j=l;j<r;j++)w[i+1][j+1]=Fast.reduce(w[i+1][j+1]+1ll*w[i][j]*a[j]);
					for(int j=r;j>l;j--)w[i+1][j-1]=Fast.reduce(w[i+1][j-1]+1ll*w[i][j]*d[j]);
				}
				res.G[x][0].resize(n);
				res.G[x][1].resize(n);
				res.G[x][2].resize(n);
				for(int i=0;i<n;i++){
					res.G[x][0][i]=Fast.reduce(res.G[x][0][i]+w[i][l]);
					res.G[x][1][i]=Fast.reduce(res.G[x][1][i]+w[i][r]);
					for(int j=l;j<=r;j++){
						res.G[x][2][i]=Fast.reduce(res.G[x][2][i]+1ll*w[i][j]*f[j]);
					}
				}
			}
			return res;
		}
		int mid=(l+r)>>1;
		auto L=divide(l,mid-1),R=divide(mid+1,r);
		auto fl=L.calc(c[mid-1]),fr=R.calc(c[r]);
		reverse(all(fl)),reverse(all(fr));
		auto ifl=inv(fl,n),ifr=inv(fr,n);
		L.mul(fl,mid-l),R.mul(fr,r-mid);
		L.mul(ifl,n),R.mul(ifr,n);
		node res;
		res.F=mul(L.F,gen(mid-1))*mul(gen(mid),R.F);
		poly h=(poly{0,c[mid]}+
			L.G[1][1]*poly{0,0,int(1ll*d[mid]*a[mid-1]%mod)}+
			R.G[0][0]*poly{0,0,int(1ll*a[mid]*d[mid+1]%mod)})%n;
		h=inv(poly{1}-h,n);
		poly p[2],q[3];
		p[0]=poly{0,a[mid-1]}*L.G[0][1]%n;
		p[1]=poly{0,d[mid+1]}*R.G[1][0]%n;
		q[0]=poly{0,d[mid]}*L.G[1][0]%n;
		q[1]=poly{0,a[mid]}*R.G[0][1]%n;
		q[2]=(poly{0,d[mid]}*L.G[1][2]+poly{0,a[mid]}*R.G[0][2]+poly{f[mid]})%n;
		Poly::init(n+n-1);
		int k=Poly::lim;
		static comp *p0[2]={buf[0],buf[1]},*p1[2]={buf[2],buf[3]};
		static comp *h0=buf[4],*h1=buf[5],*w0[2]={buf[6],buf[7]},*w1[2]={buf[8],buf[9]};
		DFT(p[0],p0[0],p1[0]);
		DFT(p[1],p0[1],p1[1]);
		DFT(h,h0,h1);
		fill(w0[0],w0[0]+k,comp(0,0));
		fill(w1[0],w1[0]+k,comp(0,0));
		inc(p0[0],p1[0],h0,h1,w0[0],w1[0]);
		fill(w0[1],w0[1]+k,comp(0,0));
		fill(w1[1],w1[1]+k,comp(0,0));
		inc(p0[1],p1[1],h0,h1,w0[1],w1[1]);
		tie(p[0],p[1])=iDFT(w0[0],w1[0],w0[1],w1[1]);
		p[0].resize(n),p[1].resize(n);
		static comp *q0[3]={buf[10],buf[11],buf[12]},*q1[3]={buf[13],buf[14],buf[15]};
		static comp *G0[2]={buf[16],buf[17]},*G1[2]={buf[18],buf[19]};
		DFT(p[0],p0[0],p1[0]);
		DFT(p[1],p0[1],p1[1]);
		for(int c:{0,1,2})DFT(q[c],q0[c],q1[c]);
		for(int j:{0,1,2}){
			for(int i:{0,1}){
				fill(G0[i],G0[i]+k,comp(0,0));
				fill(G1[i],G1[i]+k,comp(0,0));
				inc(p0[i],p1[i],q0[j],q1[j],G0[i],G1[i]);
			}
			tie(res.G[0][j],res.G[1][j])=iDFT(G0[0],G1[0],G0[1],G1[1]);
			res.G[0][j].resize(n),res.G[1][j].resize(n);
		}
		res.G[0][0]+=L.G[0][0];
		res.G[0][2]+=L.G[0][2];
		res.G[1][1]+=R.G[1][1];
		res.G[1][2]+=R.G[1][2];
		return res;
	}
	void main(){
		Poly::Init();
		scanf("%d%d%d",&n,&m,&mod);
		Fast=fastmod(mod);
		if(mod==1)puts("0"),exit(0);
		base=sqrt(mod);
		for(int i=0;i<m;i++)scanf("%d",&a[i]);
		for(int i=0;i<n;i++)scanf("%d",&b[i]);
		for(int i=0;i<=m;i++)scanf("%d",&c[i]);
		for(int i=1;i<=m;i++)scanf("%d",&d[i]);
		for(int i=0;i<=n;i++)scanf("%d",&e[i]);
		for(int i=0;i<=m;i++)scanf("%d",&f[i]);
		poly h=solve(0,n)[1];
		h.resize(n+1);
		// debug(h);
		node res=divide(0,m);
		poly f=res.calc(c[m]),g=res.G[0][2];
		reverse(all(f));
		expand(g,f,inv(f,n+1),n+1);
		// debug(f);
		// for(int i:{0,1})for(int j:{0,1,2}){
		// 	poly t;
		// 	for(int x=0;x<res.G[i][j].size()&&x<10;x++)t.push_back(res.G[i][j][x]);
		// 	debug(i,j,t);
		// }
		// debug(g,res.G[0][2],h,f);
		int ans=0;
		for(int i=0;i<=n;i++)ans=Fast.reduce(ans+1ll*h[i]*g[i]);
		cout<<ans<<endl;
	}
}
const int mod=998244353;
ll qpow(ll x,ll y=mod-2,ll ans=1){
	static const int Mod=mod-1;
	y=(y%Mod+Mod)%Mod;
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
namespace Poly{
	const int N=1<<21,g=[](){
		vector<int>p;
		int x=mod-1;
		for(int i=2;i*i<=x;i++){
			if(x%i==0)p.push_back(i);
			for(;x%i==0;x/=i);
		}
		if(x>1)p.push_back(x);
		auto chk=[&](int x){
			for(int y:p){
				if(qpow(x,(mod-1)/y)==1)return 0;
			}
			return 1;
		};
		int res=1;
		for(;!chk(res);res++);
		return res;
	}();
	int lim,rev[N],A[N],B[N],pw[N];
	void init(int n){
		for(lim=1;lim<n;lim<<=1);
		for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
	}
	void Init(){
		int x=qpow(g,(mod-1)/N);
		pw[N/2]=1;
		for(int i=N/2+1;i<N;i++)pw[i]=1ll*pw[i-1]*x%mod;
		for(int i=N/2-1;i;i--)pw[i]=pw[i<<1];
	}
	struct Init_{
		Init_(){Init();}
	}init_;
	namespace Public{
		poly Ifac(int n){
			poly ifac(n,1);
			for(int i=2;i<n;i++)ifac[i]=1ll*ifac[mod%i]*(mod-mod/i)%mod;
			for(int i=1;i<n;i++)ifac[i]=1ll*ifac[i]*ifac[i-1]%mod;
			return ifac;
		}
		void NTT(int *f,int op){
			static unsigned long long a[N];
			for(int i=0;i<lim;i++)a[i]=f[rev[i]];
			for(int len=1,x;len<lim;len<<=1){
				for(int i=0;i<lim;i+=len<<1){
					for(int j=0;j<len;j++){
						x=a[i|j|len]*pw[len|j]%mod;
						a[i|j|len]=a[i|j]+mod-x,a[i|j]+=x;
					}
				}
				if(len>>16&1){
					for(int i=0;i<lim;i++)a[i]%=mod;
				}
			}
			for(int i=0;i<lim;i++)f[i]=a[i]%mod;
			if(op<0){
				reverse(f+1,f+lim);
				int x=qpow(lim);
				for(int i=0;i<lim;i++)f[i]=1ll*f[i]*x%mod;
			}
		}
		void NTT(poly &f,int op){
			static unsigned long long a[N];
			for(int i=0;i<lim;i++)a[i]=f[rev[i]];
			for(int len=1,x;len<lim;len<<=1){
				for(int i=0;i<lim;i+=len<<1){
					for(int j=0;j<len;j++){
						x=a[i|j|len]*pw[len|j]%mod;
						a[i|j|len]=a[i|j]+mod-x,a[i|j]+=x;
					}
				}
				if(len>>16&1){
					for(int i=0;i<lim;i++)a[i]%=mod;
				}
			}
			for(int i=0;i<lim;i++)f[i]=a[i]%mod;
			if(op<0){
				reverse(f.begin()+1,f.begin()+lim);
				int x=qpow(lim);
				for(int i=0;i<lim;i++)f[i]=1ll*f[i]*x%mod;
			}
		}
		poly operator * (const poly &a,const poly &b){ // poly multiple
			int n=a.size(),m=b.size(),k=n+m-1;
			poly c(k);
			if(min(n,m)<=50){
				for(int i=0;i<n;i++){
					for(int j=0;j<m;j++){
						c[i+j]=(c[i+j]+1ll*a[i]*b[j])%mod;
					}
				}
				return c;
			}
			init(k);
			copy(all(a),A),fill(A+n,A+lim,0);
			copy(all(b),B),fill(B+m,B+lim,0);
			NTT(A,1),NTT(B,1);
			for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
			NTT(A,-1);
			for(int i=0;i<k;i++)c[i]=A[i];
			return c;
		}
		poly& operator *= (poly &a,const poly &b){
			return a=a*b;
		}
		poly& operator += (poly &a,const poly &b){
			int n=a.size(),m=b.size();
			if(n<m)a.resize(m);
			for(int i=0;i<m;i++)(a[i]+=b[i])%=mod;
			return a;
		}
		poly operator + (const poly &a,const poly &b){ // poly addition
			poly c(a);
			return c+=b;
		}
		poly& operator -= (poly &a,const poly &b){
			int n=a.size(),m=b.size();
			if(n<m)a.resize(m);
			for(int i=0;i<m;i++)(a[i]+=mod-b[i])%=mod;
			return a;
		}
		poly operator - (const poly &a,const poly &b){ // poly subtraction
			poly c(a);
			return c-=b;
		}
		poly operator - (const poly &a){
			return poly()-a;
		}
		poly& operator *= (poly &a,const int &b){
			for(int &x:a)x=1ll*x*b%mod;
			return a;
		}
		poly operator * (const poly &a,const int &b){
			poly c(a);
			return c*=b;
		}
		poly& operator /= (poly &a,const int &b){
			return a*=qpow(b);
		}
		poly operator / (const poly &a,const int &b){
			poly c(a);
			return c/=b;
		}
		poly& operator %= (poly &a,const int &b){
			if(a.size()>b)a.resize(b);
			return a;
		}
		poly operator % (const poly &a,const int &b){
			poly c(a);
			return c%=b;
		}
		poly inv(poly a,int n=-1){ // A^-1 mod x^n
			if(n==-1)n=a.size();
			if(n==1)return poly(1,1);
			int m=(n+1)/2;
			auto b=inv(a%m,m);
			init(n+m+m-2);
			a.resize(lim),b.resize(lim);
			NTT(a,1),NTT(b,1);
			for(int i=0;i<lim;i++){
				a[i]=(2+1ll*(mod-a[i])*b[i])%mod*b[i]%mod;
			}
			NTT(a,-1);
			return a%n;
		}
	}
}
using namespace Poly::Public;
const int N=2e5+10;
int n,m,p,a[N],b[N],c[N],d[N],e[N],f[N];
matrix operator * (matrix a,matrix b){
	int n=0;
	for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
		n=max(n,(int)a[i][j].size()+(int)b[j][k].size()-1);
	}
	matrix c;
	if(n<=50){
		for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
			if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
		}
		return c;
	}
	Poly::init(n),n=Poly::lim;
	for(int i:{0,1})for(int j:{0,1}){
		a[i][j].resize(n),b[i][j].resize(n),c[i][j].resize(n);
		NTT(a[i][j],1),NTT(b[i][j],1);
	}
	for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
		for(int x=0;x<n;x++)c[i][k][x]=(c[i][k][x]+1ll*a[i][j][x]*b[j][k][x])%mod;
	}
	for(int i:{0,1})for(int j:{0,1}){
		NTT(c[i][j],-1);
		for(;!c[i][j].empty()&&!c[i][j].back();c[i][j].pop_back());
	}
	return c;
}
matrix mul(matrix a,matrix b){
	matrix c;
	for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
		if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
	}
	return c;
}
vec solve(int l,int r){
	if(l==r){
		// debug("solve",l,r,vec{poly{b[l],1},poly{e[l]}});
		return vec{poly{b[l],1},poly{e[l]}};
	}
	int mid=(l+r)>>1,n=0;
	auto L=solve(l,mid),R=solve(mid+1,r);
	for(int i:{0,1})for(int j:{0,1})if(!i||!j){
		n=max(n,(int)L[i].size()+(int)R[j].size()-1);
	}
	// debug("solve",l,r);
	Poly::init(n),n=Poly::lim;
	vec t;
	L[0].resize(n),NTT(L[0],1);
	for(int i:{0,1}){
		R[i].resize(n),t[i].resize(n);
		NTT(R[i],1);
	}
	for(int i=0;i<n;i++){
		t[0][i]=1ll*L[0][i]*R[0][i]%mod;
		t[1][i]=1ll*L[0][i]*R[1][i]%mod;
	}
	NTT(t[0],-1),NTT(t[1],-1);
	for(int i:{0,1}){
		for(;!t[i].empty()&&!t[i].back();t[i].pop_back());
	}
	t[1]+=L[1];
	// debug("solve",l,r,t);
	return t;
}
struct node{
	matrix F;
	poly G[2][3];
	poly calc(int cr){
		return F[0][0]*poly{(mod-cr)%mod,1}+F[0][1];
	}
	void mul(poly g,int k){
		Poly::init(G[0][0].size()+g.size()-1);
		int n=Poly::lim;
		g.resize(n),NTT(g,1);
		for(int i:{0,1})for(int j:{0,1,2}){
			G[i][j].resize(n),NTT(G[i][j],1);
			for(int x=0;x<n;x++)G[i][j][x]=1ll*G[i][j][x]*g[x]%mod;
			NTT(G[i][j],-1),G[i][j].resize(k);
		}
	}
};
void expand(poly &a,poly f,poly g,int m){
	int n=a.size();
	if(m<=n)return a%=m,void();
	a=a*f%n*g%m;
}
const int K=300;
matrix gen(int i){
	matrix cur;
	cur[0][0]=poly{(mod-c[i])%mod,1};
	cur[0][1]=poly{int(1ll*(mod-a[i])*d[i+1]%mod)};
	cur[1][0]=poly{1};
	return cur;
}
node divide(int l,int r){
	int n=r-l+1;
	if(r-l+1<=K){
		node res;
		function<matrix(int,int)>dfs=[&](int l,int r){
			if(l==r)return gen(l);
			int mid=(l+r)>>1;
			return dfs(l,mid)*dfs(mid+1,r);
		};
		if(l<r)res.F=dfs(l,r-1);
		else res.F[0][0]=res.F[1][1]=poly{1};
		static int w[K][N];
		for(int x:{0,1}){
			for(int i=0;i<n;i++)fill(w[i]+l,w[i]+1+r,0);
			w[0][x?r:l]=1;
			for(int i=0;i+1<n;i++){
				for(int j=l;j<=r;j++)w[i+1][j]=(w[i+1][j]+1ll*w[i][j]*c[j])%mod;
				for(int j=l;j<r;j++)w[i+1][j+1]=(w[i+1][j+1]+1ll*w[i][j]*a[j])%mod;
				for(int j=r;j>l;j--)w[i+1][j-1]=(w[i+1][j-1]+1ll*w[i][j]*d[j])%mod;
			}
			res.G[x][0].resize(n);
			res.G[x][1].resize(n);
			res.G[x][2].resize(n);
			for(int i=0;i<n;i++){
				res.G[x][0][i]=(res.G[x][0][i]+w[i][l])%mod;
				res.G[x][1][i]=(res.G[x][1][i]+w[i][r])%mod;
				for(int j=l;j<=r;j++){
					res.G[x][2][i]=(res.G[x][2][i]+1ll*w[i][j]*f[j])%mod;
				}
			}
		}
		return res;
	}
	int mid=(l+r)>>1;
	auto L=divide(l,mid-1),R=divide(mid+1,r);
	auto fl=L.calc(c[mid-1]),fr=R.calc(c[r]);
	reverse(all(fl)),reverse(all(fr));
	auto ifl=inv(fl,n),ifr=inv(fr,n);
	L.mul(fl,mid-l),R.mul(fr,r-mid);
	L.mul(ifl,n),R.mul(ifr,n);
	node res;
	res.F=mul(L.F,gen(mid-1))*mul(gen(mid),R.F);
	poly h=(poly{0,c[mid]}+
		L.G[1][1]*poly{0,0,int(1ll*d[mid]*a[mid-1]%mod)}+
		R.G[0][0]*poly{0,0,int(1ll*a[mid]*d[mid+1]%mod)})%n;
	h=inv(poly{1}-h,n);
	poly p[2],q[3];
	p[0]=poly{0,a[mid-1]}*L.G[0][1]%n;
	p[1]=poly{0,d[mid+1]}*R.G[1][0]%n;
	q[0]=poly{0,d[mid]}*L.G[1][0]%n;
	q[1]=poly{0,a[mid]}*R.G[0][1]%n;
	q[2]=(poly{0,d[mid]}*L.G[1][2]+poly{0,a[mid]}*R.G[0][2]+poly{f[mid]})%n;
	Poly::init(n+n-1);
	int k=Poly::lim;
	p[0].resize(k),p[1].resize(k),h.resize(k);
	NTT(p[0],1),NTT(p[1],1),NTT(h,1);
	for(int i=0;i<k;i++){
		p[0][i]=1ll*p[0][i]*h[i]%mod;
		p[1][i]=1ll*p[1][i]*h[i]%mod;
	}
	NTT(p[0],-1),NTT(p[1],-1);
	p[0].resize(n),p[1].resize(n);
	p[0].resize(k),p[1].resize(k);
	q[0].resize(k),q[1].resize(k),q[2].resize(k);
	NTT(p[0],1),NTT(p[1],1);
	NTT(q[0],1),NTT(q[1],1),NTT(q[2],1);
	for(int i:{0,1})for(int j:{0,1,2})res.G[i][j].resize(k);
	for(int i=0;i<k;i++){
		res.G[0][0][i]=1ll*p[0][i]*q[0][i]%mod;
		res.G[0][1][i]=1ll*p[0][i]*q[1][i]%mod;
		res.G[0][2][i]=1ll*p[0][i]*q[2][i]%mod;
		res.G[1][0][i]=1ll*p[1][i]*q[0][i]%mod;
		res.G[1][1][i]=1ll*p[1][i]*q[1][i]%mod;
		res.G[1][2][i]=1ll*p[1][i]*q[2][i]%mod;
	}
	for(int i:{0,1})for(int j:{0,1,2}){
		NTT(res.G[i][j],-1),res.G[i][j].resize(n);
	}
	res.G[0][0]+=L.G[0][0];
	res.G[0][2]+=L.G[0][2];
	res.G[1][1]+=R.G[1][1];
	res.G[1][2]+=R.G[1][2];
	return res;
}
int main(){
	scanf("%d",&sid);
	if(sid==10)sub10::main(),exit(0);
	Poly::Init();
	scanf("%d%d%d",&n,&m,&p);
	for(int i=0;i<m;i++)scanf("%d",&a[i]);
	for(int i=0;i<n;i++)scanf("%d",&b[i]);
	for(int i=0;i<=m;i++)scanf("%d",&c[i]);
	for(int i=1;i<=m;i++)scanf("%d",&d[i]);
	for(int i=0;i<=n;i++)scanf("%d",&e[i]);
	for(int i=0;i<=m;i++)scanf("%d",&f[i]);
	poly h=solve(0,n)[1];
	h.resize(n+1);
	// debug(h);
	node res=divide(0,m);
	poly f=res.calc(c[m]),g=res.G[0][2];
	reverse(all(f));
	expand(g,f,inv(f,n+1),n+1);
	// debug(f);
	// for(int i:{0,1})for(int j:{0,1,2}){
	// 	poly t;
	// 	for(int x=0;x<res.G[i][j].size()&&x<10;x++)t.push_back(res.G[i][j][x]);
	// 	debug(i,j,t);
	// }
	// debug(g,res.G[0][2],h,f);
	int ans=0;
	for(int i=0;i<=n;i++)ans=(ans+1ll*h[i]*g[i])%mod;
	cout<<ans<<endl;
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
/*#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
int sid;
using poly=vector<int>;
using vec=array<poly,2>;
using matrix=array<vec,2>;
#ifdef DEBUG
ostream& operator << (ostream &out,vec a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
ostream& operator << (ostream &out,matrix a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
#endif
namespace sub10{
	int mod=998244353,base;
	using comp=complex<double>;
	struct fastmod {
	typedef unsigned long long u64;
	typedef __uint128_t u128;

	int m;
	u64 b;

	fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
	int reduce(u64 a) {
		u64 q = ((u128)a * b) >> 64;
		int r = a - q * m;
		return r < m ? r : r - m;
	}
	} Fast(2);
	namespace Poly{
		const double pi=acos(-1);
		const int N=1<<20;
		int lim,rev[N];
		comp a0[N],a1[N],b0[N],b1[N],c0[N],c1[N],c2[N],pw[N];
		void Init(){
			for(int len=1;len<N;len<<=1){
				for(int i=0;i<len;i++){
					pw[len|i]=comp(cos(pi/len*i),sin(pi/len*i));
				}
			}
		}
		void init(int n){
			for(lim=1;lim<n;lim<<=1);
			for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
		}
		namespace Public{
			void FFT(comp *a,int op){
				for(int i=0;i<lim;i++)if(rev[i]<i)swap(a[rev[i]],a[i]);
				for(int len=1;len<lim;len<<=1){
					for(int i=0;i<lim;i+=len<<1){
						for(int j=0;j<len;j++){
							comp x=a[i|j],y=a[i|j|len]*pw[len|j];
							a[i|j]=x+y,a[i|j|len]=x-y;
						}
					}
				}
				if(op<0){
					reverse(a+1,a+lim);
					for(int i=0;i<lim;i++)a[i]/=lim;
				}
			}
			void DFT(const poly &a,comp *a0,comp *a1){
				int n=a.size();
				for(int i=0;i<n;i++)a0[i]=comp(a[i]%base,a[i]/base);
				fill(a0+n,a0+lim,comp(0,0));
				FFT(a0,1);
				copy(a0,a0+lim,a1);
				reverse(a1+1,a1+lim);
				for(int i=0;i<lim;i++)a1[i]=conj(a1[i]);
				for(int i=0;i<lim;i++){
					comp p=a0[i],q=a1[i];
					a0[i]=(p+q)*comp(0.5,0);
					a1[i]=(q-p)*comp(0,0.5);
				}
			}
			poly iDFT(comp *c0,comp *c1){
				FFT(c0,-1),FFT(c1,-1);
				auto calc=[&](double x)->ll {
					if(x>0)return Fast.reduce(ll(x+0.5));
					else{
						int res=Fast.reduce(-ll(x-0.5));
						return res?mod-res:0;
					}
				};
				poly c(lim);
				for(int i=0;i<lim;i++){
					c[i]=Fast.reduce(calc(imag(c1[i]))*base*base+calc(real(c0[i]))*base+calc(real(c1[i])));
				}
				return c;
			}
			pair<poly,poly> iDFT(comp *c0,comp *c1,comp *d0,comp *d1){
				for(int i=0;i<lim;i++)c0[i]+=comp(0,1)*d0[i];
				FFT(c0,-1),FFT(c1,-1),FFT(d1,-1);
				auto calc=[&](double x)->ll {
					if(x>0)return Fast.reduce(ll(x+0.5));
					else{
						int res=Fast.reduce(-ll(x-0.5));
						return res?mod-res:0;
					}
				};
				poly c(lim),d(lim);
				for(int i=0;i<lim;i++){
					c[i]=Fast.reduce(calc(imag(c1[i]))*base*base+calc(real(c0[i]))*base+calc(real(c1[i])));
				}
				for(int i=0;i<lim;i++){
					d[i]=Fast.reduce(calc(imag(d1[i]))*base*base+calc(imag(c0[i]))*base+calc(real(d1[i])));
				}
				return make_pair(c,d);
			}
			void inc(comp *a0,comp *a1,comp *b0,comp *b1,comp *c0,comp *c1){
				for(int i=0;i<lim;i++){
					c0[i]+=a1[i]*b0[i]+a0[i]*b1[i];
					c1[i]+=a0[i]*b0[i]+comp(0,1)*a1[i]*b1[i];
				}
			}
			poly operator * (const poly &a,const poly &b){
				int n=a.size(),m=b.size(),k=n+m-1;
				if(min(n,m)<=40){
					poly c(k);
					for(int i=0;i<n;i++){
						for(int j=0;j<m;j++){
							c[i+j]=Fast.reduce(c[i+j]+1ll*a[i]*b[j]);
						}
					}
					return c;
				}
				init(k);
				DFT(a,a0,a1),DFT(b,b0,b1);
				fill(c0,c0+lim,comp(0,0));
				fill(c1,c1+lim,comp(0,0));
				inc(a0,a1,b0,b1,c0,c1);
				auto c=iDFT(c0,c1);
				return c.resize(k),c;
			}
			poly& operator *= (poly &a,const poly &b){
				return a=a*b;
			}
			poly& operator += (poly &a,const poly &b){
				int n=a.size(),m=b.size();
				if(n<m)a.resize(m);
				for(int i=0;i<m;i++)(a[i]+=b[i])>=mod&&(a[i]-=mod);
				return a;
			}
			poly operator + (const poly &a,const poly &b){
				poly c(a);
				return c+=b;
			}
			poly& operator -= (poly &a,const poly &b){
				int n=a.size(),m=b.size();
				if(n<m)a.resize(m);
				for(int i=0;i<m;i++)(a[i]-=b[i])<0&&(a[i]+=mod);
				return a;
			}
			poly operator - (const poly &a,const poly &b){
				poly c(a);
				return c-=b;
			}
			poly operator - (const poly &a){
				return poly()-a;
			}
			poly& operator *= (poly &a,const int &b){
				for(int &x:a)x=Fast.reduce(1ll*x*b);
				return a;
			}
			poly operator * (const poly &a,const int &b){
				poly c(a);
				return c*=b;
			}
			poly& operator %= (poly &a,const int &b){
				if(a.size()>b)a.resize(b);
				return a;
			}
			poly operator % (const poly &a,const int &b){
				poly c(a);
				return c%=b;
			}
			poly inv(poly a,int n=-1){
				if(n==-1)n=a.size();
				if(n==1)return poly(1,1);
				int m=(n+1)/2;
				auto b=inv(a%m,m);
				init(n+m-1);
				static comp a0[N],a1[N],b0[N],b1[N],c0[N],c1[N];
				DFT(a,a0,a1),DFT(b,b0,b1);
				fill(c0,c0+lim,comp(0,0));
				fill(c1,c1+lim,comp(0,0));
				inc(a0,a1,b0,b1,c0,c1);
				a=iDFT(c0,c1),a.resize(n);
				DFT(a,a0,a1);
				fill(c0,c0+lim,comp(0,0));
				fill(c1,c1+lim,comp(0,0));
				inc(a0,a1,b0,b1,c0,c1);
				a=iDFT(c0,c1),a.resize(n);
				return b*2-a;
			}
		}
	}
	using namespace Poly::Public;
	const int N=2e5+10,M=1<<19|10;
	int sid,n,m,a[N],b[N],c[N],d[N],e[N],f[N];
	comp buf[20][M];
	matrix operator * (matrix a,matrix b){
		int n=0;
		for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
			n=max(n,(int)a[i][j].size()+(int)b[j][k].size()-1);
		}
		matrix c;
		if(n<=50){
			for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
				if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
			}
			return c;
		}
		Poly::init(n),n=Poly::lim;
		static comp *a0[2][2]={{buf[0],buf[1]},{buf[2],buf[3]}};
		static comp *a1[2][2]={{buf[4],buf[5]},{buf[6],buf[7]}};
		static comp *b0[2][2]={{buf[8],buf[9]},{buf[10],buf[11]}};
		static comp *b1[2][2]={{buf[12],buf[13]},{buf[14],buf[15]}};
		static comp *c0=buf[16],*c1=buf[17];
		for(int i:{0,1})for(int j:{0,1}){
			DFT(a[i][j],a0[i][j],a1[i][j]);
			DFT(b[i][j],b0[i][j],b1[i][j]);
		}
		for(int i:{0,1})for(int j:{0,1}){
			fill(c0,c0+n,comp(0,0));
			fill(c1,c1+n,comp(0,0));
			for(int k:{0,1})inc(a0[i][k],a1[i][k],b0[k][j],b1[k][j],c0,c1);
			c[i][j]=iDFT(c0,c1);
			for(;!c[i][j].empty()&&!c[i][j].back();c[i][j].pop_back());
		}
		return c;
	}
	matrix mul(matrix a,matrix b){
		matrix c;
		for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
			if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
		}
		return c;
	}
	vec solve(int l,int r){
		if(l==r){
			// debug("solve",l,r,vec{poly{b[l],1},poly{e[l]}});
			return vec{poly{b[l],1},poly{e[l]}};
		}
		int mid=(l+r)>>1,n=0;
		auto L=solve(l,mid),R=solve(mid+1,r);
		for(int i:{0,1})for(int j:{0,1})if(!i||!j){
			n=max(n,(int)L[i].size()+(int)R[j].size()-1);
		}
		// debug("solve",l,r);
		Poly::init(n),n=Poly::lim;
		vec t;
		static comp *L0=buf[0],*L1=buf[1];
		static comp *R0[2]={buf[2],buf[3]},*R1[2]={buf[4],buf[5]};
		static comp *t0[2]={buf[6],buf[7]},*t1[2]={buf[8],buf[9]};
		DFT(L[0],L0,L1);
		for(int i:{0,1}){
			fill(t0[i],t0[i]+n,comp(0,0));
			fill(t1[i],t1[i]+n,comp(0,0));
			DFT(R[i],R0[i],R1[i]);
		}
		inc(L0,L1,R0[0],R1[0],t0[0],t1[0]);
		inc(L0,L1,R0[1],R1[1],t0[1],t1[1]);
		tie(t[0],t[1])=iDFT(t0[0],t1[0],t0[1],t1[1]);
		for(int i:{0,1}){
			for(;!t[i].empty()&&!t[i].back();t[i].pop_back());
		}
		t[1]+=L[1];
		// debug("solve",l,r,t);
		return t;
	}
	struct node{
		matrix F;
		poly G[2][3];
		poly calc(int cr){
			return F[0][0]*poly{(mod-cr)%mod,1}+F[0][1];
		}
		void mul(poly g,int k){
			Poly::init(G[0][0].size()+g.size()-1);
			int n=Poly::lim;
			static comp *g0=buf[0],*g1=buf[1],*w0[2]={buf[2],buf[3]},*w1[2]={buf[4],buf[5]};
			static comp *G0=buf[6],*G1=buf[7];
			DFT(g,g0,g1);
			for(int j:{0,1,2}){
				for(int i:{0,1}){
					DFT(G[i][j],G0,G1);
					fill(w0[i],w0[i]+n,comp(0,0));
					fill(w1[i],w1[i]+n,comp(0,0));
					inc(g0,g1,G0,G1,w0[i],w1[i]);
				}
				tie(G[0][j],G[1][j])=iDFT(w0[0],w1[0],w0[1],w1[1]);
				G[0][j].resize(k),G[1][j].resize(k);
			}
		}
	};
	void expand(poly &a,poly f,poly g,int m){
		int n=a.size();
		if(m<=n)return a%=m,void();
		a=a*f%n*g%m;
	}
	const int K=400;
	matrix gen(int i){
		matrix cur;
		cur[0][0]=poly{(mod-c[i])%mod,1};
		cur[0][1]=poly{int(1ll*(mod-a[i])*d[i+1]%mod)};
		cur[1][0]=poly{1};
		return cur;
	}
	node divide(int l,int r){
		int n=r-l+1;
		if(r-l+1<=K){
			node res;
			function<matrix(int,int)>dfs=[&](int l,int r){
				if(l==r)return gen(l);
				int mid=(l+r)>>1;
				return dfs(l,mid)*dfs(mid+1,r);
			};
			if(l<r)res.F=dfs(l,r-1);
			else res.F[0][0]=res.F[1][1]=poly{1};
			static int w[K][N];
			for(int x:{0,1}){
				for(int i=0;i<n;i++)fill(w[i]+l,w[i]+1+r,0);
				w[0][x?r:l]=1;
				for(int i=0;i+1<n;i++){
					for(int j=l;j<=r;j++)w[i+1][j]=Fast.reduce(w[i+1][j]+1ll*w[i][j]*c[j]);
					for(int j=l;j<r;j++)w[i+1][j+1]=Fast.reduce(w[i+1][j+1]+1ll*w[i][j]*a[j]);
					for(int j=r;j>l;j--)w[i+1][j-1]=Fast.reduce(w[i+1][j-1]+1ll*w[i][j]*d[j]);
				}
				res.G[x][0].resize(n);
				res.G[x][1].resize(n);
				res.G[x][2].resize(n);
				for(int i=0;i<n;i++){
					res.G[x][0][i]=Fast.reduce(res.G[x][0][i]+w[i][l]);
					res.G[x][1][i]=Fast.reduce(res.G[x][1][i]+w[i][r]);
					for(int j=l;j<=r;j++){
						res.G[x][2][i]=Fast.reduce(res.G[x][2][i]+1ll*w[i][j]*f[j]);
					}
				}
			}
			return res;
		}
		int mid=(l+r)>>1;
		auto L=divide(l,mid-1),R=divide(mid+1,r);
		auto fl=L.calc(c[mid-1]),fr=R.calc(c[r]);
		reverse(all(fl)),reverse(all(fr));
		auto ifl=inv(fl,n),ifr=inv(fr,n);
		L.mul(fl,mid-l),R.mul(fr,r-mid);
		L.mul(ifl,n),R.mul(ifr,n);
		node res;
		res.F=mul(L.F,gen(mid-1))*mul(gen(mid),R.F);
		poly h=(poly{0,c[mid]}+
			L.G[1][1]*poly{0,0,int(1ll*d[mid]*a[mid-1]%mod)}+
			R.G[0][0]*poly{0,0,int(1ll*a[mid]*d[mid+1]%mod)})%n;
		h=inv(poly{1}-h,n);
		poly p[2],q[3];
		p[0]=poly{0,a[mid-1]}*L.G[0][1]%n;
		p[1]=poly{0,d[mid+1]}*R.G[1][0]%n;
		q[0]=poly{0,d[mid]}*L.G[1][0]%n;
		q[1]=poly{0,a[mid]}*R.G[0][1]%n;
		q[2]=(poly{0,d[mid]}*L.G[1][2]+poly{0,a[mid]}*R.G[0][2]+poly{f[mid]})%n;
		Poly::init(n+n-1);
		int k=Poly::lim;
		static comp *p0[2]={buf[0],buf[1]},*p1[2]={buf[2],buf[3]};
		static comp *h0=buf[4],*h1=buf[5],*w0[2]={buf[6],buf[7]},*w1[2]={buf[8],buf[9]};
		DFT(p[0],p0[0],p1[0]);
		DFT(p[1],p0[1],p1[1]);
		DFT(h,h0,h1);
		fill(w0[0],w0[0]+k,comp(0,0));
		fill(w1[0],w1[0]+k,comp(0,0));
		inc(p0[0],p1[0],h0,h1,w0[0],w1[0]);
		fill(w0[1],w0[1]+k,comp(0,0));
		fill(w1[1],w1[1]+k,comp(0,0));
		inc(p0[1],p1[1],h0,h1,w0[1],w1[1]);
		tie(p[0],p[1])=iDFT(w0[0],w1[0],w0[1],w1[1]);
		p[0].resize(n),p[1].resize(n);
		static comp *q0[3]={buf[10],buf[11],buf[12]},*q1[3]={buf[13],buf[14],buf[15]};
		static comp *G0[2]={buf[16],buf[17]},*G1[2]={buf[18],buf[19]};
		DFT(p[0],p0[0],p1[0]);
		DFT(p[1],p0[1],p1[1]);
		for(int c:{0,1,2})DFT(q[c],q0[c],q1[c]);
		for(int j:{0,1,2}){
			for(int i:{0,1}){
				fill(G0[i],G0[i]+k,comp(0,0));
				fill(G1[i],G1[i]+k,comp(0,0));
				inc(p0[i],p1[i],q0[j],q1[j],G0[i],G1[i]);
			}
			tie(res.G[0][j],res.G[1][j])=iDFT(G0[0],G1[0],G0[1],G1[1]);
			res.G[0][j].resize(n),res.G[1][j].resize(n);
		}
		res.G[0][0]+=L.G[0][0];
		res.G[0][2]+=L.G[0][2];
		res.G[1][1]+=R.G[1][1];
		res.G[1][2]+=R.G[1][2];
		return res;
	}
	void main(){
		Poly::Init();
		scanf("%d%d%d",&n,&m,&mod);
		Fast=fastmod(mod);
		if(mod==1)puts("0"),exit(0);
		base=sqrt(mod);
		for(int i=0;i<m;i++)scanf("%d",&a[i]);
		for(int i=0;i<n;i++)scanf("%d",&b[i]);
		for(int i=0;i<=m;i++)scanf("%d",&c[i]);
		for(int i=1;i<=m;i++)scanf("%d",&d[i]);
		for(int i=0;i<=n;i++)scanf("%d",&e[i]);
		for(int i=0;i<=m;i++)scanf("%d",&f[i]);
		poly h=solve(0,n)[1];
		h.resize(n+1);
		// debug(h);
		node res=divide(0,m);
		poly f=res.calc(c[m]),g=res.G[0][2];
		reverse(all(f));
		expand(g,f,inv(f,n+1),n+1);
		// debug(f);
		// for(int i:{0,1})for(int j:{0,1,2}){
		// 	poly t;
		// 	for(int x=0;x<res.G[i][j].size()&&x<10;x++)t.push_back(res.G[i][j][x]);
		// 	debug(i,j,t);
		// }
		// debug(g,res.G[0][2],h,f);
		int ans=0;
		for(int i=0;i<=n;i++)ans=Fast.reduce(ans+1ll*h[i]*g[i]);
		cout<<ans<<endl;
	}
}
const int mod=998244353;
ll qpow(ll x,ll y=mod-2,ll ans=1){
	static const int Mod=mod-1;
	y=(y%Mod+Mod)%Mod;
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
namespace Poly{
	const int N=1<<21,g=[](){
		vector<int>p;
		int x=mod-1;
		for(int i=2;i*i<=x;i++){
			if(x%i==0)p.push_back(i);
			for(;x%i==0;x/=i);
		}
		if(x>1)p.push_back(x);
		auto chk=[&](int x){
			for(int y:p){
				if(qpow(x,(mod-1)/y)==1)return 0;
			}
			return 1;
		};
		int res=1;
		for(;!chk(res);res++);
		return res;
	}();
	int lim,rev[N],A[N],B[N],pw[N];
	void init(int n){
		for(lim=1;lim<n;lim<<=1);
		for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
	}
	void Init(){
		int x=qpow(g,(mod-1)/N);
		pw[N/2]=1;
		for(int i=N/2+1;i<N;i++)pw[i]=1ll*pw[i-1]*x%mod;
		for(int i=N/2-1;i;i--)pw[i]=pw[i<<1];
	}
	struct Init_{
		Init_(){Init();}
	}init_;
	namespace Public{
		poly Ifac(int n){
			poly ifac(n,1);
			for(int i=2;i<n;i++)ifac[i]=1ll*ifac[mod%i]*(mod-mod/i)%mod;
			for(int i=1;i<n;i++)ifac[i]=1ll*ifac[i]*ifac[i-1]%mod;
			return ifac;
		}
		void NTT(int *f,int op){
			static unsigned long long a[N];
			for(int i=0;i<lim;i++)a[i]=f[rev[i]];
			for(int len=1,x;len<lim;len<<=1){
				for(int i=0;i<lim;i+=len<<1){
					for(int j=0;j<len;j++){
						x=a[i|j|len]*pw[len|j]%mod;
						a[i|j|len]=a[i|j]+mod-x,a[i|j]+=x;
					}
				}
				if(len>>16&1){
					for(int i=0;i<lim;i++)a[i]%=mod;
				}
			}
			for(int i=0;i<lim;i++)f[i]=a[i]%mod;
			if(op<0){
				reverse(f+1,f+lim);
				int x=qpow(lim);
				for(int i=0;i<lim;i++)f[i]=1ll*f[i]*x%mod;
			}
		}
		void NTT(poly &f,int op){
			static unsigned long long a[N];
			for(int i=0;i<lim;i++)a[i]=f[rev[i]];
			for(int len=1,x;len<lim;len<<=1){
				for(int i=0;i<lim;i+=len<<1){
					for(int j=0;j<len;j++){
						x=a[i|j|len]*pw[len|j]%mod;
						a[i|j|len]=a[i|j]+mod-x,a[i|j]+=x;
					}
				}
				if(len>>16&1){
					for(int i=0;i<lim;i++)a[i]%=mod;
				}
			}
			for(int i=0;i<lim;i++)f[i]=a[i]%mod;
			if(op<0){
				reverse(f.begin()+1,f.begin()+lim);
				int x=qpow(lim);
				for(int i=0;i<lim;i++)f[i]=1ll*f[i]*x%mod;
			}
		}
		poly operator * (const poly &a,const poly &b){ // poly multiple
			int n=a.size(),m=b.size(),k=n+m-1;
			poly c(k);
			if(min(n,m)<=50){
				for(int i=0;i<n;i++){
					for(int j=0;j<m;j++){
						c[i+j]=(c[i+j]+1ll*a[i]*b[j])%mod;
					}
				}
				return c;
			}
			init(k);
			copy(all(a),A),fill(A+n,A+lim,0);
			copy(all(b),B),fill(B+m,B+lim,0);
			NTT(A,1),NTT(B,1);
			for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
			NTT(A,-1);
			for(int i=0;i<k;i++)c[i]=A[i];
			return c;
		}
		poly& operator *= (poly &a,const poly &b){
			return a=a*b;
		}
		poly& operator += (poly &a,const poly &b){
			int n=a.size(),m=b.size();
			if(n<m)a.resize(m);
			for(int i=0;i<m;i++)(a[i]+=b[i])%=mod;
			return a;
		}
		poly operator + (const poly &a,const poly &b){ // poly addition
			poly c(a);
			return c+=b;
		}
		poly& operator -= (poly &a,const poly &b){
			int n=a.size(),m=b.size();
			if(n<m)a.resize(m);
			for(int i=0;i<m;i++)(a[i]+=mod-b[i])%=mod;
			return a;
		}
		poly operator - (const poly &a,const poly &b){ // poly subtraction
			poly c(a);
			return c-=b;
		}
		poly operator - (const poly &a){
			return poly()-a;
		}
		poly& operator *= (poly &a,const int &b){
			for(int &x:a)x=1ll*x*b%mod;
			return a;
		}
		poly operator * (const poly &a,const int &b){
			poly c(a);
			return c*=b;
		}
		poly& operator /= (poly &a,const int &b){
			return a*=qpow(b);
		}
		poly operator / (const poly &a,const int &b){
			poly c(a);
			return c/=b;
		}
		poly& operator %= (poly &a,const int &b){
			if(a.size()>b)a.resize(b);
			return a;
		}
		poly operator % (const poly &a,const int &b){
			poly c(a);
			return c%=b;
		}
		poly inv(poly a,int n=-1){ // A^-1 mod x^n
			if(n==-1)n=a.size();
			if(n==1)return poly(1,1);
			int m=(n+1)/2;
			auto b=inv(a%m,m);
			init(n+m+m-2);
			a.resize(lim),b.resize(lim);
			NTT(a,1),NTT(b,1);
			for(int i=0;i<lim;i++){
				a[i]=(2+1ll*(mod-a[i])*b[i])%mod*b[i]%mod;
			}
			NTT(a,-1);
			return a%n;
		}
	}
}
using namespace Poly::Public;
const int N=2e5+10;
int n,m,p,a[N],b[N],c[N],d[N],e[N],f[N];
matrix operator * (matrix a,matrix b){
	int n=0;
	for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
		n=max(n,(int)a[i][j].size()+(int)b[j][k].size()-1);
	}
	matrix c;
	if(n<=50){
		for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
			if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
		}
		return c;
	}
	Poly::init(n),n=Poly::lim;
	for(int i:{0,1})for(int j:{0,1}){
		a[i][j].resize(n),b[i][j].resize(n),c[i][j].resize(n);
		NTT(a[i][j],1),NTT(b[i][j],1);
	}
	for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
		for(int x=0;x<n;x++)c[i][k][x]=(c[i][k][x]+1ll*a[i][j][x]*b[j][k][x])%mod;
	}
	for(int i:{0,1})for(int j:{0,1}){
		NTT(c[i][j],-1);
		for(;!c[i][j].empty()&&!c[i][j].back();c[i][j].pop_back());
	}
	return c;
}
matrix mul(matrix a,matrix b){
	matrix c;
	for(int i:{0,1})for(int j:{0,1})for(int k:{0,1}){
		if(!a[i][j].empty()&&!b[j][k].empty())c[i][k]+=a[i][j]*b[j][k];
	}
	return c;
}
vec solve(int l,int r){
	if(l==r){
		// debug("solve",l,r,vec{poly{b[l],1},poly{e[l]}});
		return vec{poly{b[l],1},poly{e[l]}};
	}
	int mid=(l+r)>>1,n=0;
	auto L=solve(l,mid),R=solve(mid+1,r);
	for(int i:{0,1})for(int j:{0,1})if(!i||!j){
		n=max(n,(int)L[i].size()+(int)R[j].size()-1);
	}
	// debug("solve",l,r);
	Poly::init(n),n=Poly::lim;
	vec t;
	L[0].resize(n),NTT(L[0],1);
	for(int i:{0,1}){
		R[i].resize(n),t[i].resize(n);
		NTT(R[i],1);
	}
	for(int i=0;i<n;i++){
		t[0][i]=1ll*L[0][i]*R[0][i]%mod;
		t[1][i]=1ll*L[0][i]*R[1][i]%mod;
	}
	NTT(t[0],-1),NTT(t[1],-1);
	for(int i:{0,1}){
		for(;!t[i].empty()&&!t[i].back();t[i].pop_back());
	}
	t[1]+=L[1];
	// debug("solve",l,r,t);
	return t;
}
struct node{
	matrix F;
	poly G[2][3];
	poly calc(int cr){
		return F[0][0]*poly{(mod-cr)%mod,1}+F[0][1];
	}
	void mul(poly g,int k){
		Poly::init(G[0][0].size()+g.size()-1);
		int n=Poly::lim;
		g.resize(n),NTT(g,1);
		for(int i:{0,1})for(int j:{0,1,2}){
	// debug(g,res.G[0][2],h,f);
	int ans=0;
	for(int i=0;i<=n;i++)ans=(ans+1ll*h[i]*g[i])%mod;
	cout<<ans<<endl;
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 96ms
memory: 39452kb

input:

1 5000 5000 998244353
121811167 379924090 361631583 174189813 559424693 889647308 193102812 469875055 32237660 96186933 624360154 404866088 859165067 748410791 926700198 368632735 476560636 798138824 17883437 712872225 448819400 33122704 572152288 627010263 336722521 775918346 465722630 681224329 60...

output:

698779876

result:

ok single line: '698779876'

Test #2:

score: 3
Accepted
time: 95ms
memory: 39540kb

input:

1 4999 4919 998244353
380477138 780960797 787883474 484131625 121182688 933501638 947532778 257948759 108946829 468475856 5564419 677097370 766236309 678789875 533319074 885579006 769287005 710724535 260200529 599758240 380918586 216469888 78561030 325936496 189815268 268769489 232850763 937923688 9...

output:

475720945

result:

ok single line: '475720945'

Test #3:

score: 3
Accepted
time: 143ms
memory: 39248kb

input:

1 4995 4997 998244353
267305461 291432119 107593765 530653184 893921215 15414240 991509792 601027626 313017049 827685069 650321853 385956762 140661695 303322469 142427516 910941336 265371405 731125266 512689773 723594553 552396112 379799950 43662480 666390792 938399292 144960568 817187890 428532063 ...

output:

568578871

result:

ok single line: '568578871'

Subtask #2:

score: 5
Accepted

Test #4:

score: 5
Accepted
time: 8250ms
memory: 256344kb

input:

2 200000 200000 998244353
903563506 433239074 632684755 970178226 831892753 932120646 157832416 517140217 296101978 998244343 850946564 2367119 708278025 376919151 752106478 994362560 806760771 672325565 9 958330492 343658496 153627310 330649130 983441587 829707074 135609242 706388812 325297147 4972...

output:

108905794

result:

ok single line: '108905794'

Test #5:

score: 5
Accepted
time: 8190ms
memory: 254880kb

input:

2 199910 194100 998244353
587911377 573048398 832688590 809066619 524442920 218487661 649170169 8 150333233 204150153 800582862 464558080 291668841 361834956 998244344 998244349 806341682 775965963 459031329 867640103 425129750 7 998244343 274941091 809744915 443910210 859200100 998244350 725497297 ...

output:

597176160

result:

ok single line: '597176160'

Test #6:

score: 5
Accepted
time: 8139ms
memory: 249888kb

input:

2 150810 200000 998244353
288330007 105173193 991831123 698131025 301828280 273289882 387551340 542768677 115972971 425381688 811911805 962095963 566257196 435928108 337873530 109252306 933737641 967531573 29209951 787608009 497111219 315932660 878605444 903737754 260092904 447237039 37123388 594371...

output:

78643368

result:

ok single line: '78643368'

Subtask #3:

score: 8
Accepted

Test #7:

score: 8
Accepted
time: 8251ms
memory: 254156kb

input:

3 200000 200000 998244353
493605813 622283646 579332647 528537957 211102509 336893985 106292723 166710741 443808575 180234697 744331593 252016663 693453924 975202110 519712748 174749950 250990381 584528219 619047448 641168296 914918741 785005029 433175528 400547992 845115512 278159630 227330862 6407...

output:

144815343

result:

ok single line: '144815343'

Test #8:

score: 8
Accepted
time: 8282ms
memory: 259856kb

input:

3 200000 199996 998244353
742 699221406 301 364485093 804 294 873 282584633 204 882 889 438104412 349 737559671 152908512 490 206 11 613 175 155 659898955 983 206756334 273919067 843 898 359154783 360 612 201572138 207697004 396 482 136 361 339 831490112 279585283 516749439 318 198386232 69807322 72...

output:

758876599

result:

ok single line: '758876599'

Test #9:

score: 8
Accepted
time: 7611ms
memory: 249384kb

input:

3 1 200000 998244353
734 796 543458399 920002767 990425370 338 107321680 90089647 557777271 434728777 503 709 616 850 448 884 143526194 299065437 45361809 666577969 923 492965257 850 229 769 183867189 675 463141085 791 281 718 763 240353338 711 671313626 203252664 888743426 450 223 446 542052402 565...

output:

53421494

result:

ok single line: '53421494'

Test #10:

score: 8
Accepted
time: 460ms
memory: 42260kb

input:

3 200000 1 998244353
277786488
264242127 2 319061241 5 8 2 1 51038317 673171629 267552091 920379441 5 880796442 618282833 514210179 9 8 67744028 9 1 691195881 92394487 719900388 638641507 5 663287704 4 579997250 985749664 984980853 4 519857232 4 735668111 3 7 360023171 7 7 234677046 359140782 8 5227...

output:

140453572

result:

ok single line: '140453572'

Subtask #4:

score: 8
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 8
Accepted
time: 8210ms
memory: 252544kb

input:

4 200000 200000 998244353
199752876 397435299 166254444 779278347 182416898 901682085 69090988 738092954 712758505 681482091 950425501 897402866 870967623 36849705 515322829 172446310 900429861 34423824 785446470 553333476 938968413 86270822 973639556 431435054 741273084 677434142 222677171 61928101...

output:

65201275

result:

ok single line: '65201275'

Test #12:

score: 8
Accepted
time: 495ms
memory: 148544kb

input:

4 199996 2000 998244353
865 499 31904732 259114092 967550739 255 785 143545371 699 573 216 789 553653892 329548961 451423632 886 741679575 78720133 464611720 972 242 869 294933191 351 788310280 697 861990346 731 734 701 407 401383418 835 189335197 668 758851074 250436747 962105421 562203389 11011899...

output:

85153184

result:

ok single line: '85153184'

Test #13:

score: 8
Accepted
time: 7705ms
memory: 244276kb

input:

4 40000 190000 998244353
953 586890334 906 161 524210942 327745937 100 231 970 63891350 28 370040454 628796638 275 239621470 708518643 995 351 376514813 814869235 66 742 561 483786281 5379525 603 608 274128226 256 844 662 445297819 123782163 920 957935561 621339377 26129412 763585646 451 911 5350051...

output:

99807982

result:

ok single line: '99807982'

Subtask #5:

score: 5
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #14:

score: 5
Accepted
time: 8238ms
memory: 253928kb

input:

5 200000 200000 998244353
357 270 635 81 18806969 807 433 242 242 154 347094190 96 953 893447557 497 265754515 220901127 205 958 488 212420388 457 799989458 726134433 547661079 946786926 891 955400819 664511484 701 155 791 4 845 954462573 536216065 136 54 251 481 584310172 389122260 34 527707943 300...

output:

366841924

result:

ok single line: '366841924'

Test #15:

score: 5
Accepted
time: 8223ms
memory: 240900kb

input:

5 199999 190000 998244353
930048626 861740403 534792638 856 178 908419417 742 685 40557520 132 779489457 792 468990716 153965694 395450527 688 398541680 651 789664707 703746126 579 588989999 936017101 652728925 314526790 297 962 771009949 626 192587923 377598397 654 459 187173523 857466261 567 73215...

output:

755407887

result:

ok single line: '755407887'

Subtask #6:

score: 15
Accepted

Test #16:

score: 15
Accepted
time: 8224ms
memory: 256232kb

input:

6 200000 200000 998244353
401806059 107033001 530043262 862506025 263940497 48524969 232075248 849682830 420464058 64900333 394986647 954304290 957385577 86269798 579307969 896967626 230611640 527078096 39773429 402432856 495204529 272090833 100466767 562115973 196636941 736050044 580541546 81233872...

output:

562220526

result:

ok single line: '562220526'

Test #17:

score: 15
Accepted
time: 8122ms
memory: 233032kb

input:

6 190000 180000 998244353
331419431 585273774 326021268 911984877 504951700 663 667 967180428 535316997 888573230 112066317 286249963 593 994 230 367194808 906865758 946973557 921 1 302880572 377068830 444057418 953 1000 946 906 274661283 90 345429012 719 547222223 806 856 911 970 110923264 26390908...

output:

467130256

result:

ok single line: '467130256'

Subtask #7:

score: 16
Accepted

Dependency #1:

100%
Accepted

Test #18:

score: 16
Accepted
time: 989ms
memory: 149504kb

input:

7 200000 20000 998244353
869285118 18064361 457499026 292378234 45941854 157946840 586178769 392380503 830348035 141601898 591275235 100919004 399285791 115436998 586990272 287976693 795031696 836945332 895793688 432697639 828280269 714678411 137052352 516420393 730089484 911809696 350536206 8175289...

output:

809172057

result:

ok single line: '809172057'

Test #19:

score: 16
Accepted
time: 973ms
memory: 148764kb

input:

7 200000 19810 998244353
828902663 612852451 425506197 233025854 319333441 952074173 717042023 949076193 83452305 763673071 41376007 272593034 356441893 361994505 185035237 266625028 550156798 775373755 727044232 359307823 648601627 384158945 313651668 746883203 321976362 307448064 64684150 4186580 ...

output:

560874322

result:

ok single line: '560874322'

Test #20:

score: 16
Accepted
time: 218ms
memory: 136808kb

input:

7 1000 9996 998244353
233393388 143 900 282 622 588 259300855 18722608 81440606 388097181 802 119 117027019 445 244 220 321165142 193445923 884359675 276 671093341 934763449 844222944 251 190039071 208 521 758 621 722 370522729 731 968984566 656850987 42380471 798 292 324 609 606 400 210 785 816 863...

output:

964458165

result:

ok single line: '964458165'

Test #21:

score: 16
Accepted
time: 687ms
memory: 126692kb

input:

7 200000 9919 998244353
127286538 946789972 892201793 335420070 263695484 170118086 108765927 699100677 678757948 552873985 565640470 952666657 645394702 560901257 95959026 804657734 83330667 185533959 520165719 246753496 769277586 697870667 659358703 318912135 658640680 810790915 492140504 62924551...

output:

269104705

result:

ok single line: '269104705'

Subtask #8:

score: 16
Accepted

Dependency #6:

100%
Accepted

Test #22:

score: 16
Accepted
time: 8244ms
memory: 260408kb

input:

8 200000 200000 998244353
476657058 608590028 176876078 188969399 496243267 200861994 525765121 157833667 112147905 888494665 86463084 3240780 881100059 209383369 616595337 943058640 18341235 731579551 223351112 539615902 3395185 187153519 82693410 67612463 680802074 217978817 9323483 678602864 3453...

output:

474782296

result:

ok single line: '474782296'

Test #23:

score: 16
Accepted
time: 6824ms
memory: 218904kb

input:

8 199997 170000 998244353
505360294 8 975 463 168746690 820247591 120436643 410462769 12959063 167531115 300 621 191294387 22 410 679 782371812 449088425 162807445 835 149638206 858 65 581 12 959 310569501 119222808 476951257 403 646 312711442 530 858755892 671888747 458 412 247 114 230 422058417 22...

output:

763867893

result:

ok single line: '763867893'

Test #24:

score: 16
Accepted
time: 8220ms
memory: 254328kb

input:

8 190000 199996 998244353
749 721817394 27 645 439406479 108090145 550371723 420419950 461 779 412458565 731555989 681 322 304994251 402 74 874226263 674 346 114 126 838 687147645 321419751 420 198508289 341 807392775 960572742 60398571 708697994 880 573 77 521 699 200251635 886 5466957 908 569 96 3...

output:

446047127

result:

ok single line: '446047127'

Test #25:

score: 16
Accepted
time: 8246ms
memory: 258384kb

input:

8 200000 200000 998244353
673 387 272 59 192173777 764 170183158 746432263 207 267 390 400 524 13 968340991 557741817 104800071 932539161 695618609 496396588 645 847701916 398 59229077 279708783 178114129 477 170 819671340 467175001 430861597 292163679 405 189 67855913 794507178 990487692 197409331 ...

output:

927461446

result:

ok single line: '927461446'

Test #26:

score: 16
Accepted
time: 8190ms
memory: 242388kb

input:

8 199999 190000 998244353
190706062 888680627 83397214 6 494083839 9 5 71812818 661044051 2 851345196 4 5 9 1 655271434 10 9 4 9 6 103209989 4 9 976030578 655935000 623342477 1 206077679 7 10 8 6 9 7 298401605 892975523 8 267432364 53188239 70291367 142791981 531492153 5 5 672326478 962867181 7 8679...

output:

170212793

result:

ok single line: '170212793'

Subtask #9:

score: 9
Accepted

Dependency #5:

100%
Accepted

Dependency #7:

100%
Accepted

Dependency #8:

100%
Accepted

Test #27:

score: 9
Accepted
time: 8293ms
memory: 256896kb

input:

9 200000 200000 998244353
886612651 387277498 222689570 149684757 801547216 39958935 61994466 279732876 910669986 673110448 242227789 281852762 124220159 702603904 242726522 761430846 261708466 14196264 198147684 71130471 96539799 886809411 454014179 438893638 437708905 533400975 385272485 461115839...

output:

653639881

result:

ok single line: '653639881'

Test #28:

score: 9
Accepted
time: 8232ms
memory: 257740kb

input:

9 199000 199990 998244353
929566148 214291485 906544066 298915999 689760706 271699591 482768561 898907851 81802523 554994538 134064180 501518029 641765774 423311402 134116703 391491198 791826482 649073874 696499611 279773162 697654068 669577487 356335067 571197676 194446272 321902950 667228720 31535...

output:

790075420

result:

ok single line: '790075420'

Test #29:

score: 9
Accepted
time: 8290ms
memory: 259116kb

input:

9 199997 199992 998244353
131543484 131291289 593343835 383688404 614251659 28042347 794277226 944988995 90198501 227326291 300776651 558115109 476201534 78151684 536357291 264046767 946044015 398569226 176484997 28421208 648281543 235639450 776266080 616245182 623867397 523564530 864964454 40378887...

output:

483850208

result:

ok single line: '483850208'

Test #30:

score: 9
Accepted
time: 8210ms
memory: 255252kb

input:

9 200000 200000 998244353
745599216 859346500 634928637 690647766 10273176 338563878 7698219 743763863 718373315 189069600 879813230 122401277 976417985 98413473 210957679 595554610 710895015 273465866 711019517 695658890 236226376 740332195 711573064 388099079 794053021 135899585 924688794 41508470...

output:

503071975

result:

ok single line: '503071975'

Test #31:

score: 9
Accepted
time: 8164ms
memory: 258484kb

input:

9 200000 200000 998244353
998244284 998243397 998243865 998244160 998243619 998244095 998243530 998244257 998243534 998243564 998243583 998244164 998244147 998244000 998243730 998243737 998243628 998243528 998243829 998244222 998243852 998244137 998243563 998244120 998244207 998243409 998243839 9982...

output:

359574540

result:

ok single line: '359574540'

Subtask #10:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #32:

score: 15
Accepted
time: 8650ms
memory: 364380kb

input:

10 100000 100000 856853193
287061150 779504426 21691247 494814415 381655016 536089292 240188530 458291018 332927950 428352746 351529999 258956585 651084688 268523951 338285674 719419445 165275422 367200319 35308342 563282834 763880581 117326555 284413760 207571906 703023023 622478929 212959189 34094...

output:

304611769

result:

ok single line: '304611769'

Test #33:

score: 15
Accepted
time: 8599ms
memory: 356640kb

input:

10 99996 99997 653184000
466780448 535452791 494399809 577708013 478667201 237421741 395730779 45154159 498661837 490060453 482125361 487937293 157588691 293334157 321521203 332545607 379473949 284060041 248007589 586611611 608983811 260677141 333698719 223055627 87263221 229163593 28977457 18266932...

output:

420309862

result:

ok single line: '420309862'

Test #34:

score: 15
Accepted
time: 8664ms
memory: 357096kb

input:

10 99999 90909 993244353
662162902 368244673 342499724 545049098 136506796 132436037 290223682 406097143 860074972 162846125 724197628 121400297 113044490 571603127 804520820 716276159 223707430 992306213 67492417 849796319 195226523 811081288 878152369 146106266 297648880 82596461 645880612 8404165...

output:

988875128

result:

ok single line: '988875128'

Test #35:

score: 15
Accepted
time: 8696ms
memory: 406256kb

input:

10 99939 99191 619701811
471592989 63987447 296515528 434393809 417522560 235747800 318375577 493346545 293408357 502026258 384261946 2633459 211063149 511625485 317222583 159798065 478842502 299419646 341333878 214971597 216954473 284823472 514945706 380116339 499467361 423121831 184869643 21045491...

output:

170476426

result:

ok single line: '170476426'

Test #36:

score: 15
Accepted
time: 8610ms
memory: 368940kb

input:

10 100000 100000 761140380
535267356 745353877 500892797 72821999 206782603 274141687 238741351 705785503 33076811 685974761 141313651 487155329 758438399 740389121 653321807 242325899 271642201 382683239 328197257 364100593 754134917 394678301 686138447 541301689 274967291 220724737 688145503 38492...

output:

389683306

result:

ok single line: '389683306'
English 繁體中文 简体中文

Server Time: 2024-12-03 08:31:57 | OpenSource Project