program mire;
const mo=666013;
const I3:array[1..3,1..3] of longint=( (1,0,0), (0,1,0),(0,0,1));
const o3:array[1..3,1..3] of longint=( (0,0,0), (0,0,0),(0,0,0));
type mat=array[1..3,1..3] of longint;
var f,g:text;
    n,x,y,z,a,b,c,p,i,j:longint;
    bufin,bufout:array[1..1 shl 16] of byte;
    m,s,re,fi:mat;
function im(k,q:mat; nn,mm:longint):mat;
var i,j,ss,ii,jj:longint;
begin
   for i:=1 to nn do
     for j:=1 to mm do
       begin
          ss:=0;
               for jj:=1 to nn do
                 ss:=(ss+k[i,jj]*q[jj,j]) mod mo;
           re[i,j]:=ss;
       end;
    im:=re;
end;
function ridicare(t:mat; l:longint):mat;
var i,j:longint;
begin
  s:=i3;
  while l<>0 do
     begin
       if l mod 2=1 then
           s:=im(s,t,3,3);
        t:=im(t,t,3,3);
       l:=l div 2;
     end;
   ridicare:=s;
end;
begin
  assign(f,'iepuri.in'); reset(f);
  assign(g,'iepuri.out'); rewrite(g);
  settextbuf(f,bufin); settextbuf(g,bufout);
    readln(f,p);
    for i:=1 to p do
       begin
          readln(f,x,y,z,a,b,c,n);
          m:=o3;
          m[1,2]:=1; m[2,3]:=1;
          m[3,1]:=c; m[3,2]:=b; m[3,3]:=a;
          fi[1,1]:=x; fi[2,1]:=y; fi[3,1]:=z;
          m:=ridicare(m,n);
          m:=im(m,fi,3,1) ;
          writeln(g,m[1,1] mod mo);
       end;
  close(f);
  close(g);
end.