var x,y,z,a,b,c:int64;
  f,g:text;
  i,t:0..100;
  j,n:longint;

 procedure citire;
  begin
   readln(f,x,y,z,a,b,c,n);
  end;

 procedure iepuri;
  var aux:int64;
  begin
   aux:=z*a+y*b+x*c;
   x:=y;
   y:=z;
   z:=aux;
  end;

begin
  assign(f,'iepuri.in');
  assign(g,'iepuri.out');
  reset(f);
  rewrite(g);
  readln(f,t);
  for i:=1 to t do
    begin
    citire;
    for j:=3 to n do iepuri;
    writeln(g,z mod 666013);
    end;
  close(f);
  close(g);
end.