var numowowowo,x,y,z,b,a,c,n,t,i:longint;
    u,q:text;
    iepuri:array[0..100000] of longint;
begin
//WoooOOOOoooOOOooo!
assign (u,'iepuri.in'); reset(u);
assign (q,'iepuri.out'); rewrite(q);
//X Y Z A B C N
readln(u,t);
for numowowowo:=1 to t do begin
  read(u,iepuri[0]); read(u,iepuri[1]); read(u,iepuri[2]); read(u,a); read(u,b); read(u,c); read(u,n); readln(u);
      for i:=3 to n do begin
      iepuri[i]:=(A*iepuri[i-1]) + (B*iepuri[i-2]) + (C*iepuri[i-3]);
      end;
if iepuri[n] < 666013 then writeln(q,iepuri[n])
 else if iepuri[n] = 666013 then writeln(q,0)
 else writeln(q,iepuri[n] mod 666013);
end;
close(u); close(q);
end.