var t,j:0..100;
    x,y,z:1..2000000000;
    a,c,b:1..100;
    n,s,i,q,aux:1..2000000000;
    f,g:text;
    begin
assign(f,'iepuri.in');
assign(g,'iepuri.out');
reset(f);
rewrite(g);
readln(f,t);
j:=0;
repeat
j:=j+1;
readln(f,x,y,z,a,b,c,n);
i:=2;
repeat
i:=i+1;
aux:=a*z+b*y+c*x;
x:=y;
y:=z;
z:=aux;
until i=n;
q:=aux mod 666013;
writeln(g,q);
until j=t;
{v[1]:=x;
v[2]:=y;
v[3]:=z;
for i:=4 to n+1 do v[i]:=a*v[i-1]+b*v[i-2]+c*v[i-3];
q:=v[n+1] mod 666013;
writeln(g,q);
end;     }
close(f);
close(g);
end.