#include <algorithm>
#include <iostream>
#include <iomanip>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")
 
const int MAXN = 20;
const int Mod = 104857601;
 
class FFT_GF
{
public:	
	static const int alpha=79427530;
	int Alpha[MAXN],Beta[MAXN];
	FFT_GF()
	{
		for (int i=MAXN-1,a=alpha;i>=0;i--){
			Alpha[i]=a;Beta[i]=Pow(a,Mod-2);a=Mul(a,a);
		}
	}
	int Mul(int a,int b){return (((long long)a)*b)%Mod;}
	int Add(int a,int b){long long c=(long long)a+b;if (c>=Mod)	return c-Mod;return c;}
	int Sub(int a,int b){long long c=(long long)a-b;if (c<0)return c+Mod;	return c;}
	int Pow(int a,int n){if (n==0)return 1;int r=Pow(a,n>>1);r=Mul(r,r);if (n&1)r=Mul(r,a);return r;}
	void FFT(int *A,int n){
		for (int i=0,j=0;i<(1<<n);i++){
			if (i<j)swap(A[i],A[j]);
			int high=(1<<(n-1));
			while (high&j){j^=high;high>>=1;}
			j^=high;
		}
		for (int level=0;level<n;level++){
			for (int i=0;i<(1<<n);i+=(2<<level)){
				int w=1,a=Alpha[level];
				for (int j=0,k=(1<<level);j<(1<<level);j++,k++){
					int t=Mul(A[i+k],w);
					A[i+k]=Sub(A[i+j],t);A[i+j]=Add(A[i+j],t);
					w=Mul(w,a);
				}
			}
		}
	}
	void revFFT(int *A,int n){
		for (int i=0,j=0;i<(1<<n);i++){
			if (i<j)swap(A[i],A[j]);
			int high=(1<<(n-1));
			while (high&j){j^=high;high>>=1;}
			j^=high;
		}
		for (int level=0;level<n;level++){
			for (int i=0;i<(1<<n);i+=(2<<level)){
				int w=1,a=Beta[level];
				for (int j=0,k=(1<<level);j<(1<<level);j++,k++){
					int t=Mul(A[i+k],w);
					A[i+k]=Sub(A[i+j],t);A[i+j]=Add(A[i+j],t);
					w=Mul(w,a);
				}
			}
		}
		unsigned int rep=1;
		for (int i=0;i<n;i++){
			if (!(rep&1))rep>>=1;
			else rep=(rep+Mod)>>1;
		}
	}
	void convolution(int* A, int *B, int *C, int n) // C <- A * B  (|C| = 2**n) it will destory A and B!
	{
		//cout << "FFT " << n << endl;
		FFT(A, n); FFT(B, n);
		for(int i=0;i<(1<<n);i++) C[i] = Mul(A[i], B[i]);
		revFFT(C, n);
		for(int i=0;i<(1<<n);i++) C[i] = Mul(C[i], Pow(Pow(2, n), Mod-2));
	}
}FFT_GF_solver;
 
 
int A[1<<MAXN], B[1<<MAXN], C[1<<MAXN]; // for FFT
int n;
int N = 1; // rec def length, 2^N
int a[1<<MAXN], c[1<<MAXN]; // a[1], a[2], ... a[n],  a[k] = c[1] * a[k-1] + c[2] * a[k-2] ..
int resultArray[1<<MAXN];
int moveLeft[MAXN][1<<MAXN];
 
void reduceResultArray(int k)
{
	while(k >= 8)
	{
		for(int i = 0; i < (1<<(N+1)); i++)
		{
			A[i] = 0;
			B[i] = 0;
		}
		for(int i = 0; i < (1<<N); i++)
			A[i] = moveLeft[k-1][i];
		for(int i = 0; i < (1<<(k-1)); i++)
			B[i] = resultArray[(1<<N)+(1<<(k-1))+i];
 
		FFT_GF_solver.convolution(A, B, C, N+1);
		for(int i = 1; i < (1<<N)+(1<<(k-1)); i++)
			resultArray[i] = (resultArray[i] + C[i-1]) % Mod;
		k --;
	}
 
	for(int i = (1<<N) + (1<<k) - 1; i >= (1<<N); i--)
	{
		for(int j = 0; j < (1<<N); j++)
		{
			resultArray[i - (1<<N)+j] = (resultArray[i - (1<<N)+j] + (long long)resultArray[i] * moveLeft[0][j]) % Mod;
		}
	}
}
 
void reduceResultArray2NtoN(int N)
{
	for(int pos = 3; pos >= 2; pos --)
	{
		for(int i = 0; i < (1<<(N+1)); i++)
		{
			A[i] = 0;
			B[i] = 0;
		}
		for(int i = 0; i < (1<<N); i++)
			A[i] = moveLeft[N][i];
		for(int i = 0; i < (1<<N); i++)
			B[i] = resultArray[(1<<N)*pos+i];
		FFT_GF_solver.convolution(A, B, C, N+1);
		for(int i = 1; i < (1<<(N+1)); i++)
			resultArray[i+(pos-2)*(1<<N)] = (resultArray[i+(pos-2)*(1<<N)] + C[i-1]) % Mod;
	}
}
 
void buildMoveLeft(int k)
{
	for(int i = 0; i < (1<<N); i++)
		resultArray[i] = 0;
	for(int i = 0; i < (1<<k); i++)
		resultArray[(1<<N)+i] = 0;
	resultArray[(1<<N)+(1<<k)-1] = 1;
	reduceResultArray(k);
	for(int i = 0; i < (1<<N); i++)
		moveLeft[k][i] = resultArray[i];
}
 
int x_power[1<<MAXN], x_ans[1<<MAXN];
 
int MAIN()
{
	long long k;
	cin >> n >> k;
	while((1<<N) < n) N ++;
	k += (1<<N)-n-1;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		cin >> c[i];
	memset(moveLeft, 0, sizeof(moveLeft));
	for(int i = 1; i <= n; i++)
		moveLeft[0][(1<<N)-i] = c[i];
	for(int i = 1; i <= N; i++)
		buildMoveLeft(i);
	for(int i = 0; i < (1<<(N+1)); i++)
	{
		x_power[i] = 0;
		x_ans[i] = 0;
	}
	memset(x_power, 0, sizeof(x_power));
	memset(x_ans, 0, sizeof(x_ans));
	x_power[1] = 1;
	x_ans[0] = 1;
	for(int b = 0; (1LL<<b) <= k; b++)
	{
		if((k & (1LL<<b)) > 0)
		{
			for(int i = 0; i < (1<<(N+2)); i++)
			{
				A[i] = 0;
				B[i] = 0;
			}
			for(int i = 0; i < (1<<(N+1)); i++)
			{
				A[i] = x_power[i];
				B[i] = x_ans[i];
			}
			FFT_GF_solver.convolution(A, B, C, N+2);
			for(int i = 0; i < (1<<(N+2)); i++)
				resultArray[i] = C[i];
 
			reduceResultArray2NtoN(N);
			for(int i = 0; i < (1<<(N+1)); i++)
				x_ans[i] = resultArray[i];
		}
		for(int i = 0; i < (1<<(N+2)); i++)
		{
			A[i] = 0;
			B[i] = 0;
		}
		for(int i = 0; i < (1<<(N+1)); i++)
		{
			A[i] = x_power[i];
			B[i] = x_power[i];
		}
		FFT_GF_solver.convolution(A, B, C, N+2);
		for(int i = 0; i < (1<<(N+2)); i++)
			resultArray[i] = C[i];
 
		reduceResultArray2NtoN(N);
		for(int i = 0; i < (1<<(N+1)); i++)
			x_power[i] = resultArray[i];
 
	}
	for(int i = 0; i < (1<<(N+1)); i++)
		resultArray[i] = x_ans[i];
	reduceResultArray(N);
	for(int i = 0; i < (1<<(N+1)); i++)
		x_ans[i] = resultArray[i];	
 
	long long ans = 0;
	for(int i = 1; i <= n; i++)
		ans = (ans + (long long) a[i] * x_ans[i + (1<<N) - n - 1]) % Mod;
	cout << ans << endl;
	return 0;
}
 
int main()
{
	#ifdef LOCAL_TEST
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cout << fixed << setprecision(16);
	return MAIN();
}