#include <bits/stdc++.h>

using namespace std;
const long inf = 1e9 + 9; 
    
long cp(int cp, int a) {
    long ans = 1, temp = cp;
    for (int i = 1; i <= a; i++) {
        ans *= temp--;
    }
    return ans;
}

long fac(int k) {
    if (k <= 1) return 1;
    else return k*fac(k-1);
}

long countArray(int n, int k, int x) {
    int ans = cp(k, n-2);
    ans -= 2*fac(k-1) - fac(k-2);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    int k;
    int x;
    cin >> n >> k >> x;
    long answer = countArray(n, k, x);
    answer %= inf;
    cout << answer;
    return 0;
}