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:longint;
    ms,mi:mat;



procedure putere(nr:longint);
var mp:mat;
   i,j,k:byte;
begin
   while nr>0 do
   begin
        if nr mod 2=1 then
        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]+mi[i,k]*ms[k,j]) mod 666013;
               end;
           for i:=1 to 3 do
               for j:=1 to 3 do
                  mi[i,j]:=mp[i,j];
        end;
           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]+ms[i,k]*ms[k,j]) mod 666013;
               end;
           for i:=1 to 3 do
               for j:=1 to 3 do
                  ms[i,j]:=mp[i,j];
        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.