program iepuri;
type mat=array[1..1,1..3] of longint;
     matrice=array[1..3,1..3] of longint;
var x,y,z,a1,b1,c1,n,t,k:integer;
    a,c:matrice;
    b:matrice;
    f,g:text;
const mo=666013;
procedure inmultire(var b,a:matrice);
var i,j,d:longint;
  begin
    for i:=1 to 3 do
      for j:=1 to 3 do
        begin
          c[i,j]:=0;
          for d:=1 to 3 do
            c[i,j]:=c[i,j]+a[i,d]*b[d,j];
        end;
    for i:=1 to 3 do
      for j:=1 to 3 do
        a[i,j]:=c[i,j] mod mo;
  end;
procedure exp(p:longint);
  begin
    while p>0 do
      begin
        if p mod 2 =1 then
                      begin
                        inmultire(b,a);
                        p:=p-1;
                      end
                      else
                      begin
                        p:=p div 2;
                        inmultire(b,a);
                      end;
      end;
  end;
begin
  assign(f,'iepuri.in');
  assign(g,'iepuri.out');
  reset(f);
  rewrite(g);
  readln(f,t);
  b[2,1]:=1;
  b[3,2]:=1;
  for k:=1 to t do
    begin
      readln(f,x,y,z,a1,b1,c1,n);
      b[1,3]:=c1;
      b[2,3]:=b1;
      b[3,3]:=a1;
      a[1,1]:=x;
      a[1,2]:=y;
      a[1,3]:=z;
      n:=n-2;
      exp(n);
      writeln(g,a[1,3]);
    end;
  close(f);
  close(g);
end.