Program Iepuri;

const fin = 'iepuri.in';
     fout = 'iepuri.out';

type tmatrix3x3 = array[1..3,1..3] of int64;

var t,x,y,z,a,b,c,n: longint;
                  r: array[1..100] of longint;
             tx, x3: tmatrix3x3;

function mmx(m1, m2: tmatrix3x3): tmatrix3x3;
 var i,j: byte;
begin
 for i:=1 to 3 do
     for j:=1 to 3 do
         mmx[i,j]:=((m1[i,1]*m2[1,j] mod 666013) + (m1[i,2]*m2[2,j] mod 666013)
                  +(m1[i,3]*m2[3,j] mod 666013)) mod 666013;
end;

function get(kk: longint): tmatrix3x3;
 var kkx: tmatrix3x3;
begin
 if kk = 1 then begin get:=tx; exit; end;

 if kk mod 2 = 0 then
    begin
      kkx:=get(kk div 2);
      get:=mmx(kkx, kkx);
      exit;
    end
    else
    begin
      kkx:=get(kk div 2);
      get:=mmx( mmx( kkx, kkx), tx);
      exit;
    end;
end;

procedure solve(k: longint);
 var fmx: tmatrix3x3;
begin
 tx[1,1]:=A; tx[1,2]:=B; tx[1,3]:=C;
 tx[2,1]:=1; tx[2,2]:=0; tx[2,3]:=0;
 tx[3,1]:=0; tx[3,2]:=1; tx[3,3]:=0;

 x3[1,1]:=z; x3[1,2]:=0; x3[1,3]:=0;
 x3[2,1]:=y; x3[2,2]:=0; x3[2,3]:=0;
 x3[3,1]:=x; x3[3,2]:=0; x3[3,3]:=0;

 dec(n,2);
 fmx:=get(n);
 fmx:=mmx(fmx, x3);
 r[k]:=fmx[1,1] mod 666013;
end;

procedure load;
 var f: text; i: byte;
begin
 assign(f, fin); reset(f);
  readln(f, t);
  for i:=1 to t do
      begin
        readln(f, x, y, z, a, b, c, n);
        solve(i);
      end;
 close(f);
end;

procedure save;
 var f: text; i: byte;
begin
 assign(f, fout); rewrite(f);
 for i:=1 to t-1 do
  writeln(f, r[i]);
 write(f, r[t]);
 close(f);
end;

begin
 load;
 save;
end.