#include <bits/stdc++.h>

using namespace std;

const long MOD = 1000000007;

vector<long> powersofkm1;
template <class T> 
std::ostream& operator<<(std::ostream& os, const vector<T>& rhs)
{
	cout << "[";
	for (const auto& x : rhs)
		os << x << " ";
	cout << "]";
	return os;
}


long countArray(long n, long k, long x) 
{
	vector<long> U(n+1,0);
	U[2] = 1;
	if (x == 1)
		U[2] = 0;
	
    for (long i = 3; i < U.size(); ++i)
	{
		U[i] =  powersofkm1[i-2] - U[i-1];
		U[i] %= MOD;
		if (U[i] < 0)
			U[i] += MOD;
	}
// 	cout << U << endl;
	return U[n];
}

int main() 
{
    long n;
    long k;
    long x;
    cin >> n >> k >> x;
	
	powersofkm1.resize(n+1);
	powersofkm1[0] = 1;
	for (long i = 1; i < powersofkm1.size(); ++i)
	{
		powersofkm1[i] = powersofkm1[i-1]*(k-1);
		powersofkm1[i] %= MOD;
		
	}
	
// 	cout << powersofkm1 << endl;
	
    long answer = countArray(n, k, x);
    cout << answer << endl;
    return 0;
}