#include <iostream>

using namespace std;

long MOD = 1000000007;	

long long power(long long x, long long y, long long p)
{
	long long res = 1;      // Initialize result

	x = x % p;  // Update x if it is more than or
				// equal to p

	while (y > 0)
	{
		// If y is odd, multiply x with result
		if (y & 1)
			res = (res*x) % p;

		// y must be even now
		y = y >> 1; // y = y/2
		x = (x*x) % p;
	}
	return res;
}

long long countArray(long long n, long long k, long long x) 
{
	// Return the number of ways to fill in the array.
	long long count1 = power(k-1,n-4,MOD);
	long long count2 = power(k-2,2,MOD);
	long long count3 = power(k-1,n-3,MOD);

	long long sum1 = (count1*count2) % MOD;

	return (count3 + sum1) % MOD;
}

long long countArray2(long long n, long long k, long long x)
{
	long long first=0;
	long long second=1;

	for (int i = 3; i <= n; ++i)
	{
		long long prevfirst = first;
		long long prevsecond = second;
		first = ((k - 1)*second)%MOD;
		second = (prevfirst+(((k-2)*prevsecond)%MOD))%MOD;
	}

	return x==1?first:second;
}

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