program iepuri;

type sir=array[0..4]of int64;

var a,b,c,t:integer;
    w:sir;
    n:int64;

procedure prelucrare;
var i:integer;
begin
for i:=3 to n do
    begin
    w[3]:=w[2]*a+w[1]*b+w[0]*c;
    w[0]:=w[1];
    w[1]:=w[2];
    w[2]:=w[3];
    end;
end;

procedure scriere;
var q:int64;
begin
q:=w[3] mod 666031;
writeln(q);
end;

procedure citire;
var i:integer;
begin
assign(input,'iepuri.in');
reset(input);
readln(t);
for i:=1 to t do
    begin
    readln(w[0],w[1],w[2],a,b,c,n);
    prelucrare;
    scriere;
    end;
close(input);
end;

begin
assign(output,'iepuri.out');
rewrite(output);
citire;
close(output);
end.