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
             v1:=(z*a)mod rest;
             v2:=(y*b)mod rest;
             v3:=(x*c)mod rest;
             v4:=(v1+v2+v3)mod rest;
             x:=y;
             y:=z;
             z:=v4;
           end;
        writeln(g,z);
     end;
 close(g);
 end.