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