const modulo=666013;
var     t,i:byte;
        x,y,z,k:int64;
        a,b,c,n:longint;
        j:longint;
        f1,f2:text;
begin
  assign(f1,'iepuri.in');
  reset(f1);
  assign(f2,'iepuri.out');
  rewrite(f2);
  readln(f1,t);
  for i:=1 to t do
    begin
      readln(f1,x,y,z,a,b,c,n);
      for j:=3 to n do
        begin
          k:=((a*z)mod modulo+(b*y)mod modulo+(c*x)mod modulo)mod modulo;
          x:=y;
          y:=z;
          z:=k;
        end;
      writeln(f2,k);
    end;
  close(f1);
  close(f2);
end.