type mat=array[1..3,1..3]of longint;

var f,g:text;
    a,b,c:1..1000;
    x,y,z:1..10000;
    u,t:byte;
    i,n:longint;
    s,s0,s1,s2:longint;
    ms,mi:mat;


procedure prod_mat(var mp:mat; m1,m2:mat);
var i,j,k:byte;
begin
   for i:=1 to 3 do
      for j:=1 to 3 do
      begin
         mp[i,j]:=0;
         for k:=1 to n do
            mp[i,j]:=(mp[i,j]+m1[i,k]*m2[k,j]) mod 666013;
      end;
end;

procedure copiaza(m1: mat; var m2:mat);
var i,j:byte;
begin
   for i:=1 to n do
      for j:=1 to n do
         m2[i,j]:=m1[i,j];
end;

procedure putere(nr:longint);
var mt:mat;
begin
   while nr>0 do
   begin
        if nr mod 2=1 then
        begin
            prod_mat(mi,mi,ms);
        end;
        prod_mat(ms,ms,ms); {ms la patrat}
        nr:=nr div 2;
   end;
end;




begin
     assign(f,'iepuri.in');
     assign(g,'iepuri.out');
     reset(f);
     rewrite(g);
     read(f,t);
     for u:=1 to t do
     BEGIN
         READ(f,X,Y,Z,A,B,C,N);
{         S0:=X;
         S1:=Y;
         S2:=Z;
      FOR I:=3 TO N DO
         BEGIN
         S:=(A*S2+B*S1+C*S0)mod 666013;
         S0:=S1;
         S1:=S2;
         S2:=S;
      END;
          }
      {matricea solutie}
      ms[1,1]:=a; ms[1,2]:=b; ms[1,3]:=c;
      ms[2,1]:=1; ms[2,2]:=0; ms[2,3]:=0;
      ms[3,1]:=0; ms[3,2]:=1; ms[3,3]:=0;
      {matrice I}
      mi[1,1]:=1; mi[1,2]:=0; mi[1,3]:=0;
      mi[2,1]:=0; mi[2,2]:=1; mi[2,3]:=0;
      mi[3,1]:=0; mi[3,2]:=0; mi[3,3]:=1;
      putere(n-2);
      s:=(mi[1,1]*z+mi[1,2]*y+mi[1,3]*x)mod 666013;
      WRITELN(G,S);



     END;
     close(f);
     close(g);
end.