program iepuri;
  const modul=666013;
  var t,k,i,x,y,z,a,b,c,n:longint;
      m,m1,pow:array [1..3,1..3] of int64;


begin
  assign(input,'iepuri.in');
  reset(input);
  assign(output,'iepuri.out');
  rewrite(output);

  readln(t);
  for k:=1 to t do
    begin
      readln(x,y,z,a,b,c,n);n:=n-2;
      m[3,1]:=x;m[3,2]:=y;m[3,3]:=z;
      pow[1,3]:=c;pow[2,1]:=1;pow[2,3]:=b;pow[3,2]:=1;pow[3,3]:=a;
      m1:=pow;
      while n>0 do
        begin
          if n mod 2=1 then
            begin
              m1:=m;
              m[1,1]:=(m1[1,1]*pow[1,1]+m1[1,2]*pow[2,1]+m1[1,3]*pow[3,1])mod modul;
              m[1,2]:=(m1[1,1]*pow[1,2]+m1[1,2]*pow[2,2]+m1[1,3]*pow[3,2])mod modul;
              m[1,3]:=(m1[1,1]*pow[1,3]+m1[1,2]*pow[2,3]+m1[1,3]*pow[3,3])mod modul;
              m[2,1]:=(m1[2,1]*pow[1,1]+m1[2,2]*pow[2,1]+m1[2,3]*pow[3,1])mod modul;
              m[2,2]:=(m1[2,1]*pow[1,2]+m1[2,2]*pow[2,2]+m1[2,3]*pow[3,2])mod modul;
              m[2,3]:=(m1[2,1]*pow[1,3]+m1[2,2]*pow[2,3]+m1[2,3]*pow[3,3])mod modul;
              m[3,1]:=(m1[3,1]*pow[1,1]+m1[3,2]*pow[2,1]+m1[3,3]*pow[3,1])mod modul;
              m[3,2]:=(m1[3,1]*pow[1,2]+m1[3,2]*pow[2,2]+m1[3,3]*pow[3,2])mod modul;
              m[3,3]:=(m1[3,1]*pow[1,3]+m1[3,2]*pow[2,3]+m1[3,3]*pow[3,3])mod modul;

            end;
                   m1:=pow;
              pow[1,1]:=(m1[1,1]*m1[1,1]+m1[1,2]*m1[2,1]+m1[1,3]*m1[3,1])mod modul;
              pow[1,2]:=(m1[1,1]*m1[1,2]+m1[1,2]*m1[2,2]+m1[1,3]*m1[3,2])mod modul;
              pow[1,3]:=(m1[1,1]*m1[1,3]+m1[1,2]*m1[2,3]+m1[1,3]*m1[3,3])mod modul;
              pow[2,1]:=(m1[2,1]*m1[1,1]+m1[2,2]*m1[2,1]+m1[2,3]*m1[3,1])mod modul;
              pow[2,2]:=(m1[2,1]*m1[1,2]+m1[2,2]*m1[2,2]+m1[2,3]*m1[3,2])mod modul;
              pow[2,3]:=(m1[2,1]*m1[1,3]+m1[2,2]*m1[2,3]+m1[2,3]*m1[3,3])mod modul;
              pow[3,1]:=(m1[3,1]*m1[1,1]+m1[3,2]*m1[2,1]+m1[3,3]*m1[3,1])mod modul;
              pow[3,2]:=(m1[3,1]*m1[1,2]+m1[3,2]*m1[2,2]+m1[3,3]*m1[3,2])mod modul;
              pow[3,3]:=(m1[3,1]*m1[1,3]+m1[3,2]*m1[2,3]+m1[3,3]*m1[3,3])mod modul;
          n:=n div 2;

        end;
      writeln(m[3,3]);
    end;
  close(output);
end.