#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read()
{
  ll x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9')
  {
    if (ch == '-')
      f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
  {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
ll T,a,b,n,m,mod=1000000009,fac[1000005],inv[1000005];
ll qp(ll a,ll b){
	ll t=a,res=1;
	while(b){
		if(b%2)
			res=res*t%mod;
		t=t*t%mod,b>>=1;
	}
	return res;
}
ll mul(ll a,ll b,ll c){
	return a*b%mod*c%mod;
}
ll C(ll n,ll m){
	return mul(fac[n],inv[n-m],inv[m]); 
}
int main(){
	T=read();
	fac[0]=inv[0]=1;
	for(int i=1;i<=1e6;i++)
		inv[i]=qp(fac[i]=fac[i-1]*i%mod,mod-2);
	while(T--){
		a=read(),b=read(),n=read(),m=read();
		if(m<1||m>n)
			puts("0");
		else
			printf("%d\n",mul(qp(a,n-m),qp(b,m-1),C(n-1,m-1)));
	}
	return 0;
}