#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

long countArray(long n, long k, long x) {
    long ans=1;
    long temp=0;
    if(x==1){
    	temp=1;
    }
    else{
    	temp=0;
    }
    for(int i=2;i<=n;i++){
    	temp=(ans-temp+MOD)%MOD;
    	ans=((k*ans)%MOD-ans+MOD)%MOD;
    }
    return temp;
}

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