#include <bits/stdc++.h>

using namespace std;

struct matrix{
    long a11;
    long a12;
    long a21;
    long a22;
    matrix(long a, long b, long c, long d){
        a11=a;
        a12=b;
        a21=c;
        a22=d;
    }
};

struct matrix mat_mul(struct matrix x , struct matrix y){
    long m = 1000000007;
    long a11 = ((x.a11%m*y.a11%m)%m + (x.a12%m*y.a21%m)%m)%m;
    long a12 = ((x.a11%m*y.a12%m)%m + (x.a12%m*y.a22%m)%m)%m;
    long a21 = ((x.a21%m*y.a11%m)%m + (x.a22%m*y.a21%m)%m)%m;
    long a22 = ((x.a21%m*y.a12%m)%m + (x.a22%m*y.a22%m)%m)%m;
    return matrix(a11,a12,a21,a22);
}

struct matrix mat_exp(struct matrix m , int n){
    if(n==0) return matrix(1,0,0,1);
    else if(n==1) return m;
    else if(n%2==0) return mat_mul(mat_exp(m,n/2),mat_exp(m,n/2));
    else return mat_mul(m,mat_mul(mat_exp(m,n/2),mat_exp(m,n/2)));
}

long countArray(int n, int k, int x) {
    long m = 1000000007; 
    struct matrix mat = matrix(0,k-1,1,k-2);
    matrix m1 = mat_exp(mat,n-3);
    if(x==1)
        return ((m1.a11*(k-1))%m + (m1.a12*(k-2))%m)%m;
    else return ((m1.a21*(k-1))%m + (m1.a22*(k-2))%m)%m;
}

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