#include <bits/stdc++.h>
#define ll long long int
#define M 1000000009

using namespace std;

int power(ll x,ll n)
{
    int result=1;
    while(n>0)
    {
        if(n%2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}
long long int countArray(ll n, ll k, ll x) {
    
    ll ans=(power(k-1,n-3))  *   (k-2) + 1;
    return ans;
}

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