var T,i:byte;
    a,b,c:integer;
    n,f1,f2,f3,f4,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;
  repeat
    f4:=f3*a+f2*b+f1*c;
    f1:=f2;
    f2:=f3;
    f3:=f4;
    zi:=zi+1;
  until (zi=n);
  writeln(g,f4 mod 666013);
end;
close(g);
end.