program gaju;
const q=666013;
type mat=array[1..3,1..3]of longint;
var f,g:text;
v,v1:mat;
i,t,a,b,c,x,y,z,n:longint;

    procedure inmultire(var a:mat;b:mat);
    var i,j,k:byte;
       x:longint;
       c:mat;
   begin
   for i:=1 to 3 do
       for j:=1 to 3 do begin
           c[i,j]:=0;
           for k:=1 to 3 do begin
           x:=(a[i,k]*b[k,j])mod q;
           c[i,j]:=(c[i,j]+x)mod q;
       end;end;
   a:=c;
   end;

   procedure executa(n:longint);
   begin
   if n=1 then v:=v1
          else if n mod 2=0 then begin
                                   executa(n div 2);
                                   inmultire(v,v);
                                  end
                             else begin
                                  executa(n-1);
                                   inmultire(v,v1);
                                  end;
   end;


   begin
   assign(f,'iepuri1.in');reset(f);
   assign(g,'iepuri.out');rewrite(g);
   readln(f,t);
   for i:=1 to t do begin
       readln(f,x,y,z,a,b,c,n);
       v[1,1]:=0;v[1,2]:=1;v[1,3]:=0;
       v[2,1]:=0;v[2,2]:=0;v[2,3]:=1;
       v[3,1]:=c;v[3,2]:=b;v[3,3]:=a;
       v1:=v;
       executa(n);
       v1[1,1]:=x;v1[1,2]:=0;v1[1,3]:=0;
       v1[2,1]:=y;v1[2,2]:=0;V1[2,3]:=0;
       v1[3,1]:=z;v1[3,2]:=0;v1[3,3]:=0;
       inmultire(v,v1);
       writeln(g,v[1,1]);
   end;
   close(f);close(g);
   end.