#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10,G=3,Gi=332748118,mod=998244353; int n,k,a[maxn],b[maxn],fail[maxn]; inline int add(int a,int b){if((a+=b)>=mod)a-=mod;return a;} inline int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } namespace Poly{ const int maxn=1e6+10; int rev[maxn],mul[maxn],c1[maxn],c2[maxn]; void init(int n){ up(i,1,(1<<n)-1){ rev[i]=rev[i>>1]>>1; if(i&1)rev[i]|=(1<<n-1); } } void ntt(int n,int *a,int op){ n=__lg(n); init(n);up(i,0,(1<<n)-1)if(i<rev[i])swap(a[i],a[rev[i]]); for(int k=1;k<(1<<n);k<<=1){ int val=qp(op==1?G:Gi,(mod-1)/k/2); mul[0]=1;up(j,1,k-1)mul[j]=mul[j-1]*1ll*val%mod; for(int i=0;i<(1<<n);i+=k<<1){ up(j,i,i+k-1){ int L=a[j],R=a[j+k]*1ll*mul[j-i]%mod; a[j]=add(L,R),a[j+k]=add(L,mod-R); } } } if(op==-1){ int iv=qp(1<<n,mod-2); up(i,0,(1<<n)-1)a[i]=a[i]*1ll*iv%mod; } } vector<int> conv(vector<int>a,vector<int>b){ int n=a.size(),m=b.size(); int T=1;while(n+m+1>=T)T*=2; up(i,0,T-1)c1[i]=c2[i]=0; up(i,0,n-1)c1[i]=a[i]; up(i,0,m-1)c2[i]=b[i]; ntt(T,c1,1),ntt(T,c2,1); up(i,0,T-1)c1[i]=c1[i]*1ll*c2[i]%mod; ntt(T,c1,-1);vector<int>C; up(i,0,n+m-2)C.p_b(c1[i]); return C; } } int kmp(int n,int m,int *a,int *b){ if(!n)return 0; int p=0; up(i,2,n){ while(p&&a[p+1]!=a[i])p=fail[p]; if(a[p+1]==a[i])p++;fail[i]=p; }p=0; up(i,1,m){ while(p&&a[p+1]!=b[i])p=fail[p]; if(a[p+1]==b[i])p++; if(p==n)return i-n; } return -1; } int jc[maxn],jc_inv[maxn]; void init(){ int n=1e5; jc[0]=1;up(i,1,n)jc[i]=jc[i-1]*1llu*i%mod; jc_inv[n]=qp(jc[n],mod-2);down(i,n,1)jc_inv[i-1]=jc_inv[i]*1llu*i%mod; } inline int cal(int n,int m){return jc[m]*1llu*jc_inv[m-n]%mod*1llu*jc_inv[n]%mod;} void slv(){init(); n=read(),k=read()+1;k=min(k,n); up(i,1,n)a[i]=read(); up(i,1,n)b[i]=b[i+n]=read(); vector<int> A(n+1,0),B(2*n+1,0),C(k+1,0); up(i,1,n)A[i]=a[i];up(i,1,2*n)B[i]=b[i]; up(i,0,k){C[i]=cal(i,k);if(i&1)C[i]=mod-C[i];} A=Poly::conv(A,C),B=Poly::conv(B,C); up(i,1,n)a[i]=A[i];up(i,1,2*n)b[i]=B[i]; cout<<kmp(n-k,2*n-k,a+k,b+k); } int main(){ //freopen("rail.in","r",stdin),freopen("rail.out","w",stdout); slv(); return 0; }