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