#include <bits/stdc++.h>

#define MOD 1000000009

int Power(int n, int k, int mod)
{
    if (k == 0)
       return 1;

    long int p = Power(n, k/2, mod);
    p = (p * p) % mod;
    return (int)(0 == (k % 2))? p : ((n * p) % mod);
}

using namespace std;

long countArray(int n, int k, int x) {
    long int pow = Power(k-1, k-1, MOD);
    
    long int term = ((long int) (k -1)) * (n-3) % MOD;
    
    if (1 != x)
    {
        if (n % 2)
            term += 1;
        else
            term -= 1;
    }
    //std::cout << n << " "<< k << " "<< x << " " << pow << " " << term << std::endl;
    
    return (pow - term) % MOD;
}

int main() {
    int n;
    int k;
    int x;
    cin >> n >> k >> x;
    long answer = countArray(n, k, x);
    cout << answer << endl;
    return 0;
}