program iepuri;
type vect = array [0..99000000000] of longint;
var Q : vect;
    t,x,y,z,a,b,c,n,i,l : integer;
    f,g : text;
begin
assign(f,'iepuri.in');
reset(f);
readln(f,T);
l := 0;
assign(g,'iepuri.out');
rewrite(g);
repeat

readln(f,x,y,z,a,b,c,n);
Q[0] := x;
Q[1] := y;
Q[2] := z;

for i := 3 to n do
Q[i] := Q[i-3]*c+Q[i-2]*b+Q[i-1]*a;

writeln(g,Q[n] mod 666013);

l := l+1;

until l=T;

close(f);
close(g);

end.