program iepuri;
var n:longint;a,b,c,x,y,z,i:integer;f,g:text;t:byte;
function suma(n:longint):int64;
var j:longint;
begin
if n=0 then suma:=x
        else
        if n=1 then suma:=y
                else
        if n=2 then suma:=z
                else
suma:=suma(n-1)*a+suma(n-2)*b+suma(n-3)*c;
end;
begin
assign(f,'iepuri.in');reset(f);
assign(g,'iepuri.out');rewrite(g);
readln(f,t);
for i:=1 to t do
begin
readln(f,x,y,z,a,b,c,n);
writeln(g,suma(n) mod 666013);
end;
close(f);
close(g);
end.