#include<bits/stdc++.h>

using namespace std;
const int maxi=1e6+2;

const long long mo=1e9+7;
int n,k,x;

long long dp1[maxi],dp2[maxi],dp3[maxi];

int main()
{
    cin>>n>>k>>x;

    if (k==2)
    {
        if (x%2==n%2) cout<<1<<"\n"; else cout<<0<<"\n";
        return 0;
    }
    if (x==1)
    {

       dp1[1]=1;
       dp2[1]=0;
       for (int i=2;i<=n;i++)
       {
           dp1[i]=dp2[i-1];
           dp2[i]=(1ll*(k-1)*dp1[i-1] + 1ll*dp2[i-1]*(k-2))%mo;
       }

      cout<<dp1[n];
     return 0;
    }

    dp1[1]=1;
    dp2[1]=0;
    dp3[1]=0;

    for (int i=2;i<=n;i++)
      {
           dp1[i]=(dp2[i-1]+dp3[i-1])%mo;
           dp2[i]=(1ll*(k-3)*dp2[i-1]+1ll*(k-2)*dp1[i-1]+1ll*(k-2)*dp3[i-1])%mo;
           dp3[i]=(dp2[i-1]+dp1[i-1])%mo;
      }

    cout<<dp3[n]<<"\n";
    return 0;
}