1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9+7;
const int N = 3005;

ll dp[N];
ll M[N];

int main(){
    ios_base::sync_with_stdio(0);
    ll n,m;
    cin >> n >> m;

    M[0] = 1;
    for(int i=1; i<N; ++i){
        M[i] = (M[i-1]*m)%MOD;
    }

    dp[0]=1;
    dp[1]=0;
    dp[2]=1;
    for(int i=3; i<=n; ++i){
        dp[i] = 0;
//        cout << "I:" << i;
        for(int x=0; x<=i-2; ++x){
//            cout << "\n x:" << x << " i-x-2:" << i-x-2 << " dp[i-x-2]:" << dp[i-x-2] << " M[x]:" << M[x];
            dp[i] += (dp[i-x-2] * M[x]) % MOD;
            dp[i] %= MOD;
        }
//        cout << "\ndp:" << dp[i] << endl;
    }
    cout << (dp[n]*m)%MOD;
    return 0;
}