#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007
typedef long long int ll;

ll powe(ll a,ll b){
    if(b==0){
        return 1;
    }
    ll chota=powe(a,b/2);
    
    if(b&1){
        return ((chota*chota)%mod*a)%mod;
    }
    else{
        return (chota*chota)%mod;
    }
}

ll dp[1000005];

ll countArray(ll n, ll k, ll x) {
       
       if(dp[n]!=-1){
           return dp[n];
       }
       
       else if(n==3){
           if(x==1){
               dp[n]=k-1;
           }
           else
            dp[n]=k-2;
       }
       else{
           ll ans=powe(k-1,n-2)- countArray(n-1,k,x);
           if(ans<0){
               ans=(ans+mod)%mod;
           }
           else{
               ans=ans%mod;
           }
           dp[n]=ans;
       }
       
       return dp[n];
}


int main() {
    memset(dp,-1,sizeof(dp));
    ll n,k,x;
    cin >> n >> k >> x;
    ll answer = countArray(n, k, x);
    cout << dp[n]<< endl;
    return 0;
}