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
39
40
41
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int MOD = 1000000000 + 7;

int power(long long base, int pow) {
    long long res = 1;
    while(pow > 0) {
        if(pow % 2 == 1) {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        pow /= 2;
    }
    return int(res);
}

int F(int n, int x) {
    if(n <= 1) {
        return 0;
    }
    return power(x, n - 1);
}

int S(int n, int x) {
    long long res = F(n, x);
    for(int i = 2; i <= n - 2; ++i) {
        res += S(i, x) * S(n - i, x - 1);
        res %= MOD;
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    cout << S(n, m) << endl;
}