var f,g:text;
x,y,z,a,b,c,i,nr1,t,j:integer;
n:longint;
nr:array[1..100] of longint;
begin
assign(f,'iepuri.in'); reset(f);
assign(g,'iepuri.out');rewrite(g);
readln(f,t);
for j:=1 to t do
 begin
  read(f,x,y,z,a,b,c,n);
    nr[1]:=x;
    nr[2]:=y;
    nr[3]:=z;
    for i:=3 to n+1 do
    nr[i]:=a*nr[i-1]+b*nr[i-2]+c*nr[i-3];
    nr1:=nr[n+1] mod 666013;
    writeln(g,nr1);
    for i:=1 to n do nr[i]:=0;
    nr1:=0;
    n:=0;     x:=0;y:=0;z:=0;
  readln(f);
 end;
close(f);
close(g);
end.