#include <bits/stdc++.h>

using namespace std;

const long MOD = 1000000009;


long fact(int maxi, int mini)
{
    if(maxi == mini)
        return 1;
    return (maxi%MOD)*fact(maxi-1, mini);
}

int main()
{
    int n, k, x;
    cin >> n >> k >> x;
    n -= 2;
    if(n < k - n);
        n = k - n;

long no = MOD;
long bo = fact(n,1);
long to = 0;
long t = 1;
long q = no / bo;
long r = no - q * bo;
while(r > 0)
{
      long temp = to - q * t;
      if (temp == 0)
        temp = temp%MOD;
        else
      temp = MOD - ((-temp)%MOD);
      to = t;
      t = temp;
      no = bo;
      bo = r;
      q = no / bo;
      r = no - q * bo;
}
if(bo != 1)
    {
        cout << 0 << endl;
        return 0;
    }

cout << (t*fact(k, k - n))%MOD << endl;



    return 0;
}