var j,t,i,a,b,c,n:integer;
  x:array [0..1000000000] of integer;

begin
  assign(input,'iepuri.in');
  assign(output,'iepuri.out');
  reset(input);
  rewrite(output);
  readln(t);
  for j:=1 to t do
  begin
    read(a);
    x[0]:=a mod 666013;
    read(a);
    x[1]:=a mod 666013;
    read(a);
    x[2]:=a mod 666013;
    readln(a,b,c,n);
    for i:=3 to n do
      x[i]:=(a*x[i-1]+b*x[i-2]+c*x[i-3]) mod 666013;
    writeln(x[n]);
  end;
  close(input);
  close(output);
end.