program matrice5;
  const modul=10007;
  var t,n,m,k,p,i,x,d:longint;
      ans:int64;

begin
  assign(input,'matrice5.in');
  reset(input);
  assign(output,'matrice5.out');
  rewrite(output);
  readln(t);
  for i:=1 to t do
    begin
      readln(n,m,p,k);
      ans:=1;
      x:=n*m;
      d:=p;
      while x>0 do
        begin
          if x mod 2 =1 then ans:=(ans*d)mod modul;
          d:=(d*d)mod modul;
          x:=x div 2;
        end;
      x:=(n-1)*(m-1); d:=k;
      while x>0 do
        begin
          if x mod 2 =1 then ans:=(ans*d)mod modul;
          d:=(d*d)mod modul;
          x:=x div 2;
        end;

      writeln(ans);
    end;
  close(output);
end.