#include <stdio.h>

#define MODULO 10000

int n;

void mul(int a[105][105], int b[105][105], int n)
 {
  int i,j,k;
  int c[105][105];
  
  for (i=0; i<n; i++) for (j=0; j<n; j++)
   {
    c[i][j]=0;
    for (k=0; k<n; k++) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MODULO;
   }
  for (i=0; i<n; i++) for (j=0; j<n; j++) a[i][j]=c[i][j];
 }

/* b := a^n */
void pow(int a[105][105], int b[105][105], int n, int k)
 {
  if (n==0)
   {
    int i;
    memset(b, 0, sizeof(b));
    for (i=0; i<k; i++) b[i][i]=0;
    return;
   }
  if (n==1)
   {
    int i, j;
    for (i=0; i<k; i++) for (j=0; j<k; j++) b[i][j]=a[i][j];
    return;
   }
  pow(a, b, n/2, k);
  mul(b, b, k);
  if (n&1) mul(b, a, k);
 }

int main()
 {
  int k;
  int orig[105];
  int b[105];
  int a[105][105];
  int c[105][105];
  int ex;
  int s;
  
  while(1)
   {
    int i;
    scanf("%d ", &k);
    if (k==0) break;

    for (i=0; i<k; i++) scanf("%d ", &orig[i]);
    for (i=0; i<k; i++) scanf("%d ", &b[i]);
    memset(a, 0, sizeof(a));
    for (i=0; i<k; i++) a[0][i]=b[i];
    for (i=1; i<k; i++) a[i][i-1]=1;
    scanf("%d ", &ex);

    if (ex<k)
     {
      printf("%d\n", orig[ex]);
     }
    else
     {
      pow(a, c, ex-(k-1), k);
/*
      for (i=0;i<k;i++)
       {
        int j;
        for (j=0; j<k; j++) printf("%d ", c[i][j]);
        printf("\n");
       }
*/
      s=0;
      for (i=0;i<k;i++) s=(s+orig[k-1-i]*c[0][i])%MODULO;
    
      printf("%d\n", s);
     }
   }
  return 0;
 }