# SDOI2008[递归数列(版本II)]

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-25

DESCRIPTION:

*/

#include <iostream>

#include <string.h>

using namespace std;

const int LOG2_MAXN=60;

const int MAXK=15;

typedef long long int matrix[MAXK][MAXK];

int k;

matrix A,B;

long long int m,n;

int p;

void mul(matrix A,matrix B,matrix C)

{

memset(C,0,sizeof(matrix));

for (int i=0;i<k;i++)

for (int j=0;j<k;j++)

for (int K=0;K<k;K++)

C[i][j]=(C[i][j]+A[i][K]*B[K][j])%p;

}

void mul(int a,int b,int c,matrix A,matrix B,matrix C)

{

memset(C,0,sizeof(matrix));

for (int i=0;i<a;i++)

for (int j=0;j<b;j++)

for (int k=0;k<c;k++)

C[i][j]=(C[i][j]+A[i][k]*B[k][j])%p;

}

void power(long long int n,matrix A)

{

static bool calced;

static matrix T[LOG2_MAXN];

if (!calced)

{

calced=true;

memcpy(T[0],B,sizeof(matrix));

for (int i=1;i<LOG2_MAXN;i++) mul(T[i-1],T[i-1],T[i]);

}

memset(A,0,sizeof(matrix));

for (int i=0;i<k;i++) A[i][i]=1;

int t=0;

while (n!=0)

{

if (n%2)

{

matrix AT;

mul(A,T[t],AT);

memcpy(A,AT,sizeof(matrix));

}

t++;

n/=2;

}

}

void get(matrix S,long long int n)

{

if (n==0) memset(S,0,sizeof(matrix));

else if (n%2==0)

{

matrix a,b;

get(a,n>>1);

power(n>>1,b);

for (int i=0;i<k;i++) b[i][i]=(b[i][i]+1)%p;

mul(a,b,S);

}

else

{

matrix a,b;

get(a,n-1);

power(n-1,b);

for (int i=0;i<k;i++)

for (int j=0;j<k;j++)

S[i][j]=(a[i][j]+b[i][j])%p;

}

}

int main()

{

cin>>k;

for (int i=0;i<k;i++) cin>>A[0][i];

for (int i=0;i<k;i++) cin>>B[k-i-1][k-1];

for (int i=1;i<k;i++) B[i][i-1]=1;

cin>>m>>n>>p;

matrix S;

matrix AXS;

get(S,m-1);

mul(1,k,k,A,S,AXS);

int a=AXS[0][0];

get(S,n);

mul(1,k,k,A,S,AXS);

int b=AXS[0][0];

cout<<((b-a)%p+p)%p<<endl;

}