#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace acac
{
	
	inline int read()
	{
		int ans=0,fh=1;
		char ch=getchar();
		while(ch<'0'||ch>'9')
		{
			if(ch=='-')fh=-1;
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')
		{
			ans=ans*10+ch-'0';
			ch=getchar();
		}
		return ans*fh;
	}

	int n,m,k,Len;
	const int mod=998244353;
	int wz[400010];
	int yg[400010],qaq[400010];
	int A[400010],C[400010],B[2][400010],X[400010],Y[400010],DA[400010],DC[400010];
	int jl[400010];
	
	
	void print(int A[],int n)//项数 
	{
		cout<<n<<": "; 
		for(int i=0;i<n;i++)
		{
			cout<<A[i]<<' ';			
		}
		cout<<'\n';
	}
	

	inline int ksm(int a,int k,int ok)
	{
		int ans=1,bs=a;
		while(k)
		{
			if(k&1)ans=1ll*bs*ans%mod;
			bs=1ll*bs*bs%mod;
			k>>=1;
		}
		return ans;
	}
	
	inline void pre(int xz,int w)
	{
		for(int i=1;i<xz;i++)
		{
			wz[i]=(wz[i>>1]>>1)|((i&1)<<w);
		}
	}
	void init(int n)
	{
		int tot=0;

		for(int i=2;i<=(n<<1);i<<=1)
		{
			yg[++tot]=ksm(3,(mod-1)/i,0);
		}
	}
	int ook;
	inline void NTT(int n,int A[],int tmp)
	{
		
		for(int i=1;i<n;i++)
		{
		
			if(i<wz[i])swap(A[wz[i]],A[i]);
		}
		int tot=0;
		for(int mid=1;(mid<<1)<=n;mid<<=1)
		{
			int len=(mid<<1);
			int num;
			num=yg[++tot];
			for(int j=0;j<n;j+=len)
			{
				int w=1;
				for(int i=j;i<mid+j;i++)
				{
					int v=1ll*w*A[i+mid]%mod;//卡常
					A[i+mid]=A[i]-v;
					while(A[i+mid]<0)A[i+mid]+=mod;
					A[i]=A[i]+v;
					while(A[i]>=mod)A[i]-=mod;
					
					w=1ll*w*num%mod;
				}
			}
		}
		if(tmp==-1)
		{
			reverse(A+1,A+n);			
			int now=ksm(n,mod-2,1);
			jl[n]=now;			
			for(int i=0;i<n;i++)
			{
				A[i]=1ll*A[i]*now%mod; 
			}
		}
	}
	
	inline void cf(int n,int A[],int B[])
	{
    	for(int i=0;i<(n>>1);i++)
    	{
    		X[i]=A[i],Y[i]=B[i];
		}
		
		NTT(n,X,1),NTT(n,Y,1);
		for(int i=0;i<n;i++)
		{
			X[i]=1ll*X[i]*Y[i]%mod;
		}
		
		NTT(n,X,-1);
		for(int i=0;i<n;i++)
		{
			A[i]=X[i];
			X[i]=Y[i]=0;
			
		}
		//cout<<endl;
	}
	
	
	
	int t;
	
	inline void solve(int m,int A[])
	{
	//	memset(B,0,sizeof(B));
		B[0][0]=ksm(A[0],mod-2,0);
		t=0;
		int len=1;
		int Len=2;
		//cout<<m<<endl;
		while(Len<=m)
		{
			Len<<=1;
			len=(int)floor(log(Len)/log(2)+0.3)-1;
			pre(Len,len);
			t^=1;
		//	memset(B[t],0,sizeof(B[t]));
			for(int i=0;i<=Len;i++)
			{
				B[t][i]=B[t^1][i]*2;
				if(B[t][i]>=mod)B[t][i]-=mod;
			//	cout<<B[t][i]<<' ';
			}
			cf(Len,B[t^1],B[t^1]);
			cf(Len,B[t^1],A);
			for(int i=0;i<=Len;i++)
			{
				B[t][i]=B[t][i]-B[t^1][i];
				if(B[t][i]<0)B[t][i]+=mod;
			}
		//	print(B[t],Len+1);
		//	bas<<=1,Len<<=1,len++;
		//	if(bas<m)pre(Len,len);
		}
	}
	
	inline int qn(int yn,int n,int A[])//最高次 
	{
		memset(B,0,sizeof(B));
		int Len=2;
		int m=n;
		Len=log(m)/log(2)+1;
		Len=(1<<Len);
		solve(Len,A);
		for(int i=0;i<=yn;i++)
		{
			A[i]=0;
		}
		for(int i=0;i<Len;i++)
		{
			A[i]=B[t][i];
		//	cout<<B[t][i]<<' ';
			//cout<<i<<endl;
			B[t][i]=B[t^1][i]=0;
		}

		return Len*2;
	}
	
	int ANS[4000010];
	int CD;
	
	int fc(int n,int m,int A[],int C[],int ANS2[])//A项数，B项数 
	{
		//print(A,n);
		if(n<m)
		{
			for(int i=0;i<m;i++)
			{
				ANS2[i]=A[i];
				
			}
			return Len;
		}
	//	memset(DA,0,sizeof(DA));

		for(int i=0;i<=n;i++)
		{
			DA[n-i]=A[i];
		}
		for(int i=n-m+1;i<=n;i++)
		{
			DA[i]=0;
		}
	//	print(DC,n);
	//	cout<<"()";
		
		int cd=CD;
		
		cd=log(n*4)/log(2)+1;
		cd=(1<<cd);
		pre(cd,(int)floor(log(cd)/log(2)+0.3)-1);
		//print(DC,cd);
		cf(cd,DA,DC);
		
		reverse(DA,DA+n-m+1);
		
		for(int i=n-m+1;i<=n;i++)
		{
			DA[i]=0;
		}
//		for(int i=0;i<=n-m;i++)
//		{
//			C[i]=DA[i];
//		}
		cd=n*4;
		cd=log(cd)/log(2)+1;
		cd=(1<<cd);
		pre(cd,(int)log(cd)/log(2));
		cf(cd,DA,C);
		
		ok=0;
		
		for(int i=0;i<m;i++)
		{
			ANS2[i]=A[i]-DA[i];
			if(ANS2[i]<0)ANS2[i]+=mod;
		}
	
		for(int i=m;i<=cd;i++)
		{
			ANS2[i]=0;
		}
		return cd;
	}
	
	int f[1000010],tz[1000010],BS[1000010];
	
	int qm(int Len,int p,int A[],int B[],int op)
	{
		int awa=min(k*2,p);
		pre(Len,(int)floor(log(Len)/log(2)+0.3)-1);
		cf(Len,A,B);
		Len=fc(awa,k,A,tz,qaq);
		for(int i=0;i<=Len;i++)
		{
			A[i]=qaq[i];
		}
		return Len;
		
	}
	

	int main()
	{
		init(200000);
		
		n=read(),k=read();
		for(int i=1;i<=k;i++)
		{
			f[i]=read();
			while(f[i]<0)f[i]+=mod;
			while(f[i]>mod)f[i]-=mod;
		}
		for(int i=0;i<k;i++)
		{
			A[i]=read();
			while(A[i]<0)A[i]+=mod;
			while(A[i]>mod)A[i]-=mod;
		}
		Len=log(k*2)/log(2)+1;
		Len=(1<<Len);
		for(int i=1;i<=k;i++)
		{
			tz[k-i]=DC[k-i]=(mod-f[i]);
			if(DC[k-i]>=mod)DC[k-i]-=mod;
			if(tz[k-i]>=mod)tz[k-i]-=mod;
		}
		tz[k]=DC[k]=1;
		reverse(DC,DC+k+1);
		int qer=log(n)/log(2);
		if((1<<qer)<n)qer++;
		CD=qn(k,min((2ll<<qer),2ll*k)-k+1,DC);
		ANS[0]=BS[1]=1;
		int i=1;
		while(n)
		{
		
			if(n&1)
			{
				Len=qm(Len,2*k,ANS,BS,1);
			}
			if((1<<(i-1))>=(k<<1))--i;
			Len=qm(Len,(2<<i),BS,BS,0);
			i++;
			n>>=1;
		}
		//print(A,k);
		ll ans=0;
		for(int i=0;i<k;i++)
		{
			ans+=1ll*A[i]*ANS[i]%mod;
			if(ans>=mod)ans-=mod;
		}
		cout<<ans;
		return 0;
	}
 } 
int main()
{
//	freopen("P4723_1.in","r",stdin);
//	freopen("out.out","w",stdout);
	acac::main();
	return 0;
}
/*
1 4
3 -1 0 4
-2 3 1 5
*/

这东西运行时间是时限的两倍，是哪里出问题了吗QWQ