var f,g:text;
s,q,i,j,x,y,z,a,b,c,n:longint;

begin
assign(g,'iepuri.out');
rewrite(g);
assign(f,'iepuri.in');
reset(f);
readln(f,q);
for i:=1 to q do
begin
s:=0;
readln(f,x,y,z,a,b,c,n);

for j:=3 to n do
begin
s:=x*a+y*b+c*z;
c:=b;
b:=a;
a:=s;
end;
writeln(g,s mod 666013);
end;

close(f);
close(g);
end.