var i,j,t,n,aux1,a,b,c,z,x,y:longint;
begin
assign(input,'iepuri.in');
assign(output,'iepuri.out');
reset(input);
rewrite(output);
readln(t);
for i:=1 to t do
  begin
   read(x,y,z,a,b,c,n);
   for j:=3 to n do
     begin
      aux1:=z;
      z:=x*c+y*b+z*a;
      x:=y;
      y:=aux1;
     end;
   x:=x mod 666013;
   y:=y mod 666013;
   z:=z mod 666013;
   writeln(z);
  end;
close(input);
close(output);
end.