program f;
type TMatrix = array[1..100,1..100] of longint;
var Exp:array[0..50] of TMatrix;
    A,B:array[1..100] of longint;
    Res,Res2:TMatrix;
    XRes,XRes2,XRes3:^TMatrix;
    Index1,Index2,Index:longint;
    I1:longint;
    K:longint;
    Vysl:longint;
procedure MUL(var M1:TMatrix;var M2:TMatrix;var M3:TMatrix);
var r,s,i:longint;
    Ctr:longint;
begin
   for r:=1 to k do 
      for s:=1 to k do begin
         Ctr:=0;
	 for i:=1 to k do 
	    Ctr:=(Ctr+(M1[r,i]*M2[i,s])) mod 10000;
	 M3[r,s]:=Ctr;
      end;
end;
begin
   read(K);
   while (k<>0) do begin
      for index:=1 to K do
         read(A[index]);
      for index:=1 to K do 
         read(B[index]);
      for Index1:=1 to K do for Index2:=1 to K do Exp[0][Index1,Index2]:=0;
      for index:=1 to K-1 do 
         Exp[0][index+1,index]:=1;
      for index:=1 to K do 
         Exp[0][index,K]:=B[K-index+1];
      read(Index);
      if (Index<K) then
         writeln(A[Index+1])
      else begin
         Index1:=Index shr 1;
	 I1:=0;
	 while (Index1<>0) do begin
	    MUL(Exp[I1],Exp[I1],Exp[I1+1]);
	    Index1:=Index1 shr 1;
	    inc(I1);
	 end;
	 for index1:=1 to 100 do for index2:=1 to 100 do Res[index1,index2]:=0;
	 For index1:=1 to 100 do Res[index1,index1]:=1;
	 XRes:=@Res;
	 XRes2:=@Res2;
	 I1:=0;
	 while (Index>0) do begin
	    if (Index and 1)=1 then begin
	       Mul(XRes^,Exp[I1],XRes2^);
	       XRes3:=XRes2;
	       XRes2:=XRes;
	       XRes:=XRes3;
	    end;
	    Index:=Index shr 1;
	    inc(I1);
	 end;
	 Vysl:=0;
         for index1:=1 to k do 
	    Vysl:=(Vysl+(A[index1]*XRes^[index1,1])) mod 10000;
	writeln(Vysl);    
      end;
      read(K);
   end;
end.