#include <stdio.h>

long int a[150], b[150], k, i;
long int lasta[150];
long int ActInd;
int count;
long int first;

long int geta(long int ind, long int k)
{
	if ( ind < k ) return a[ind];
	
	long int sum = 0;
	for (int j=1; j<=k; j++)
	{
		sum += geta(ind-j,k)*b[j-1];
		sum %= 10000;
	}
	return sum;
}

long int geta2(long int ind, long int k)
{
	if (ind < k) return a[ind];
	return lasta[(ind-k) % k];
}

int main()
{
	scanf("%li", &k);
	if ( k ) {
		for (int j = 0; j < k; j++) scanf("%li", &a[j]);
		for (int j = 0; j < k; j++) scanf("%li", &b[j]);
		scanf("%li\n",&i);
	}

	while ( k )
	{
		long int suma;// = geta(i,k);
		if (i<k) suma = a[i];
		else {
			ActInd = 0;
			count = 0;
			first = k;
			for (int j=k; j<=i; j++)
			{
				suma = 0;
				for(int l=1; l<=k; l++)
				{
					suma += geta2(j-l,k)*b[l-1];
					suma %= 10000;
				}
				lasta[(j-k) % k] = suma;
			}
			suma = lasta[(i-k) % k];
		}

		printf("%li\n",suma);
		
		scanf("%li", &k);
		if ( k ) {
		  for (int j = 0; j < k; j++) scanf("%li", &a[j]);
		  for (int j = 0; j < k; j++) scanf("%li", &b[j]);
		  scanf("%li\n",&i);
		}
	}
	
	return 0;
}