#include <stdio.h>

#define MAX 100
#define MOD 10000

unsigned int n;
unsigned int a[MAX], b[MAX];
unsigned int P[MAX][MAX], Q[MAX][MAX], R[MAX][MAX];

static void mcopy(unsigned int x[MAX][MAX], unsigned int y[MAX][MAX])
{
	unsigned int i,j;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
			y[i][j] = x[i][j];
}

static void mmul(unsigned int x[MAX][MAX], unsigned int y[MAX][MAX], unsigned int z[MAX][MAX])
{
	unsigned int i,j,k;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++) {
			z[i][j] = 0;
			for (k=0; k<n; k++)
				z[i][j] = (z[i][j] + x[i][k]*y[k][j]) % MOD;
		}
}

unsigned int zth(unsigned int z)
{
	unsigned int i,j,out;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
			P[i][j] = Q[i][j] = 0;
	for (i=0; i<n-1; i++)
		Q[i][i+1] = 1;
	for (i=0; i<n; i++)
		Q[n-1][n-1-i] = b[i];
	for (i=0; i<n; i++)
		P[i][i] = 1;
	while (z) {
		if (z & 1) {
			mcopy(P, R);
			mmul(Q, R, P);
		}
		mcopy(Q, R);
		mmul(R, R, Q);
		z >>= 1;
	}
	out = 0;
	for (i=0; i<n; i++)
		out = (out + a[i]*P[0][i]) % MOD;
	return out;
}

int main(void)
{
	unsigned int i;
	for(;;) {
		scanf("%d", &n);
		if (!n)
			return 0;
		for (i=0; i<n; i++)
			scanf("%d", &a[i]);
		for (i=0; i<n; i++)
			scanf("%d", &b[i]);
		scanf("%d", &i);
		printf("%d\n", zth(i));
	}
}