#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define MOD 1000000009
#define MAX 210

void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
  ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;
  r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
  while(r1>0){
    q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1;
    r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
  }
  *c=r0; *a=a0; *b=b0;
}

ll get_inv(ll n, ll p){
  ll a,b,c;
  extended_euclid(n,p,&c,&a,&b);
  if(a<p) a+=p;
  return a%p;
}

ll pw(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}


ll fact[MAX], fact_inv[MAX];
ll inv[MAX];

ll P(int a, int b){
  if(b < 0 || b > a) return 0;
  return (fact[a] * fact_inv[a-b])%MOD;
}

int main(){
  int i, j;
  int N, M, K;
  int T;
  ll f[MAX], ff[MAX], res;
  ll C[MAX][MAX];

  REP(i,1,MAX) inv[i] = get_inv(i, MOD);
  
  fact[0] = fact_inv[0] = 1;
  REP(i,1,MAX) fact[i] = (fact[i-1] * i)%MOD;
  REP(i,1,MAX) fact_inv[i] = (fact_inv[i-1] * inv[i])%MOD;

  rep(i,MAX) C[0][i] = 0;
  rep(i,MAX) C[i][0] = 1;
  REP(i,1,MAX) REP(j,1,MAX) C[i][j] = (C[i-1][j-1] + C[i-1][j])%MOD;

  scanf("%d",&T);
  while(T--){
    scanf("%d%d%d",&N,&M,&K);

    REP(i,1,N+1){
      if(K < M) ff[i] = (P(i, K) * pw(i-K, M-K, MOD))%MOD;
      else      ff[i] = P(i, M);
      REP(j,1,i) ff[i] = (ff[i] - ff[j]*C[i][j]) % MOD;
      if(ff[i] < 0) ff[i] += MOD;
      f[i] = (ff[i] * fact_inv[i])%MOD;
    }

    res = 0;
    REP(i,1,N+1) res += f[i];
    res %= MOD;
    printf("%d\n",(int)res);
  }

  return 0;
}