飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4973

题意很明显，就是相邻两个人如果一样，则一定要大于k

因为第i+1个人和第i个人的选择有关，一共有四种可能，就是i选择<=k i+1选择<=k ；i选择<=k i+1选择>k;i选择>k i+1选择<=k ；i选择>k i+1选择>k 。所以我们很容易想到矩阵，令mat[2][2]其中a i_j表示四种中得一种，则我们只要有一个A[k,m-k] ,则答案就为A*(mat)^(n-1);//

//  main.cpp
//  zoj3690
//
//  Created by cfhaiteeh on 14/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define  LL long long
using namespace  std;
const int MOD=1000000007;
struct Matrix{
   LL  mat[3][3];
};
int n,m,k;
Matrix MUL(Matrix a,Matrix b){
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
            }
        }
    }
    return c;
}
Matrix poww(Matrix a,int k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=1;i<=2;i++)ans.mat[i][i]=1;
    while(k!=0){
        if(k%2==1){
            ans=MUL(ans,a);
        }
        a=MUL(a,a);
        k/=2;
    }
    return ans;
}
Matrix a;
LL ai[3];
void init(){
    memset(a.mat,0,sizeof(a.mat));
    ai[1]=k;
    ai[2]=m-k;
    int a1=k-1;
    if(a1<0)a1=0;
    a.mat[1][1]=a1;
    a.mat[1][2]=m-k;
    a.mat[2][1]=k;
    a.mat[2][2]=m-k;
}
LL ans[3];
void play(){
    Matrix c=poww(a, n-1);
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            ans[i]=(ans[i]+ai[j]*c.mat[j][i])%MOD;
        }
    }
    
}
void pri(){
    printf("%lld\n",(ans[1]+ans[2])%MOD);
}
int main() {
    // insert code here...
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        init();
        play();
        pri();
    }
    return 0;
}