const rest=666013;
var f,g:text;
v1,v2,v3,v4,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,x,y,z,a,b,c,n);
        for i:=3 to n do
           begin
             v4:=(a*z+b*y+c*x)mod rest;
             x:=y;
             y:=z;
             z:=v4;
           end;
        writeln(g,z);
     end;
 close(g);
 end.