type iepuri=record
     a,b,c,x,y,z,n:longint;
     end;
var v:array[0..200000000] of longint;
     k:iepuri;
     j,t,m:word;
     f,g:text;
function zi():longint;
 var i,a,b,c:longint;
 begin
  a:=k.a;
  b:=k.b;
  c:=k.c;
  for i:=3 to m do
   v[i]:=(v[i-1]*a)+(v[i-2]*b)+(v[i-3]*c);
  zi:=v[k.n] mod 666013;
  end;
begin
 assign(f,'iepuri.in');
 reset(f);
 readln(f,t);
 assign(g,'iepuri.out');
 rewrite(g);
 for j:=1 to t do begin
  read(f,k.x);
  read(f,k.y);
  read(f,k.z);
  read(f,k.a);
  read(f,k.b);
  read(f,k.c);
  read(f,k.n);
  v[0]:=k.x;
  v[1]:=k.y;
  v[2]:=k.z;
  m:=k.n;
  writeln(g,zi);
  end;
 close(f);
 close(g);
end.