var f,g:text;
    t,o,i,j,a,b,c,x,y,z,n,h:longint;
begin
    assign(f,'iepuri.in'); reset(f);
    assign(g,'iepuri.out'); rewrite(g);
    readln(f,t);
    for o:=1 to t do
       begin
          read(f,x,y,z,a,b,c,n);
          for i:=3 to n do
             begin
                h:=a*z+b*y+c*x;
                x:=y;
                y:=z;
                z:=h;
             end;
          writeln(g,h mod 666013);
       end;
    close(f); close(g);
end.