#include <stdio.h>

#define MAX_K 105
int b[MAX_K];
int a[MAX_K];
int k;
int n;

struct matice {
  int m[MAX_K][MAX_K];
};

struct matice M;
struct matice POW[2],RES[2];

void nasob(struct matice *a,struct matice *b,struct matice *c) {
  int i,j,l;
  for (i=0;i<k;i++)
    for (j=0;j<k;j++) {
      int h=0;
      int *apt=a->m[i];
      for (l=0;l<k;l++) {
	h=(h+(*apt++)*b->m[l][j]);
	if (!(l&16)) h%=10000;
      }
      c->m[i][j]=h%10000;
    }
}

void mocni(int e) {
  int i,j;
  POW[0]=M;

  for (i=0;i<k;i++) 
    for (j=0;j<k;j++) RES[0].m[i][j]=i==j;

  i=0;j=0;
  while (e) {
    if (e&1) /*tuhle mocninu ano*/ {
      nasob(&RES[j],&POW[i],&RES[1-j]);
      j=j^1;
    }
    nasob(&POW[i],&POW[i],&POW[1-i]);
    i=i^1;
    e/=2;
  }
  M=RES[j];
}

int main(void) {
  int i,j;
  int res;

  while (scanf("%d",&k),k) {
    for (i=0;i<k;i++) scanf("%d",a+i);
    for (i=0;i<k;i++) scanf("%d",b+i);
    scanf("%d",&n);

    if (n<k) {printf("%d\n",a[n]);}
    else {
      for (i=0;i<k;i++)
	for (j=0;j<k;j++) {
	  if (i==k-1) M.m[i][j]=b[k-j-1];
	  else if (i+1==j) M.m[i][j]=1;
	  else M.m[i][j]=0;
	}
      
      mocni(n-k+1);
      res=0;
      for (i=0;i<k;i++) res=(res+M.m[k-1][i]*a[i])%10000;

      printf("%d\n",res);
    }

  }

  return 0;
}