var T,i:byte;
    a,b,c:integer;
    n,f1,f2,f3,f4,x,y,z,zi:longint;
    f,g:text;
begin
assign(f,'iepuri.in'); reset(f);
assign(g,'iepuri.out'); rewrite(g);
read(f,t);
for i:=1 to t do begin
  read(f,f1,f2,f3,a,b,c,n);
  zi:=2;
  x:=f1; y:=f2; z:=f3;
  repeat
    f4:=f3*a+f2*b+f1*c;
    f1:=f2;
    f2:=f3;
    f3:=f4;
    zi:=zi+1;
  until (zi=n);
  if (n<>0) and (n<>1) and (n<>2) then writeln(g,f4 mod 666013);
  if n=0 then writeln(g,x);
  if n=1 then writeln(g,y);
  if n=2 then writeln(g,z);
end;
close(g);
end.