#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

static ull const kMod = 1000000007;


// m + n (mod p)    (0 <= m < p, 0 <= n < p)
#define iaddm(m, n, p)  ((((ull)m) + ((ull)n)) % ((ull)p))

// m * n (mod p)    (0 <= m < p, 0 <= n < p)
#define imulm(m, n, p)  ((((ull)m) * ((ull)n)) % ((ull)p))

long countArray(int n, int k, int x) 
{
    ull ew = 0 /* end with x */, eo = 0 /* don't end with x */;    
    if (1 == x) ew = 1;
    else eo = 1;
    
    for (int i = 1; i < n-1; i++)
    {
        ull const pew = ew, peo = eo;
        ew = peo;
        eo = iaddm(imulm(pew, k-1, kMod), imulm(peo, k-2, kMod), kMod);
    }
    
    return eo;
}

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