var z,t,aux,n,p:int64;
    x:array[1..3]of int64;
    a:array[1..3] of int64;
    j,i:longint;
begin
  assign(input,'iepuri.in');reset(input);
  assign(output,'iepuri.out');rewrite(output);
  readln (t);
  for i:=1 to t do begin
  read(x[1],x[2],x[3],a[1],a[2],a[3],n);
  for j:=1 to n-2 do begin
   aux:=x[1]*a[3]+x[2]*a[2]+x[3]*a[1];
   x[1]:=x[2] mod 666013;
   x[2]:=x[3] mod 666013;
   x[3]:=aux mod 666013;
  end;
  writeln (aux mod 666013);
 end;
 close(input);close(output);
end.