var g,f:text;
x,y,z,a,b,c,z3,i,n,t,j:integer;
begin
assign(f,'iepuri.in');reset(f);
assign(g,'iepuri.out');rewrite(g);
readln(f,t);
for i:=1 to t do
      begin
      readln(f,x,y,z,a,b,c,n);z3:=0;
      for j:=3 to n do
          begin
          z3:=a*z+b*y+c*x;
          x:=y;
          y:=z;
          z:=z3;
          end;
      writeln(g,(666013 mod z3));
      end;
close(f);
close(g);
end.