#include <stdio.h>

#define MAX 120
#define M 10000

int k;

typedef int vec[MAX][MAX];

void cpy(vec *kam, vec *co)
{
	int i, j;
	for (i=0; i<k; i++) for (j=0;j<k; j++) (*kam)[i][j]=(*co)[i][j];
}

void mul(vec *kam, vec *a, vec *b)
{
	int i, j, m, ss;
	for (i=0; i<k; i++) for (j=0; j<k; j++)
	{
		ss=0;
		for (m=0; m<k; m++)
		{
			ss=(ss+(*a)[i][m]*(*b)[m][j])%M;
		}
		(*kam)[i][j]=ss;
	}
}

int main(void)
{
	int i, j, ss;
	vec a, b, c;
	int A[MAX];
	long long int n;

	while (scanf("%d ", &k), k)
	{
		for (i=0; i<k; i++) scanf("%d ", &A[i]);
		for (i=0; i<k; i++) for (j=0; j<k; j++) a[i][j]=b[i][j]=0;
		for (i=0; i<k-1; i++) a[i+1][i]=1;
		for (i=0; i<k; i++) scanf("%d ", &a[k-i-1][k-1]);
		for (i=0; i<k; i++) b[i][i]=1;

		scanf("%lld ", &n);
		while (n)
		{
			if (n%2)
			{
				mul(&c, &b, &a);
				cpy(&b, &c);
			}
			mul(&c, &a, &a);
			cpy(&a, &c);
			n/=2;
		}

		ss=0;
		for (i=0; i<k; i++)
		{
			ss=(ss+A[i]*b[i][0])%M;
		}
		printf("%d\n", ss);
	}

	return 0;
}