const nmax=2000000;
const rest=666013;
var f,g:text;
v:array[0..nmax]of longint;
t,x,y,z,a,b,c,n,i,j:longint;
begin
 assign(f,'iepuri.in');
 reset(f);
 assign(g,'iepuri.out');
 rewrite(g);
 readln(f,t);
 for j:=1 to t do
     begin
        readln(f,v[0],v[1],v[2],a,b,c,n);
        for i:=3 to n do
          v[i]:=(v[i-3]*c)+(v[i-2]*b)+(v[i-1]*a)mod rest;
        writeln(g,v[n]);
     end;
 close(g);
 end.