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 <iostream>
using namespace std;

const int MODULO = 1000000000 + 7;
int fastPot(long long p, unsigned int w)
{
    if(w == 0) return 1;
    if(w == 1) return p;
    int x = 1;
    while(w > 0)
    {
        if (w % 2 == 1)
            x = (int)((x * (p % MODULO)) % MODULO);
        p *= p;
        w /= 2; 
    }
    return x;
}

int calc(int len, int x, int all)
{
    if(x <= 0) return 0;
	if(len == 1) return 0;
    if(len == 2) return x;
    return (
        fastPot(x, len - 1) % MODULO + 
        (
			(calc(len - 2, x, all) % MODULO) * 
            (calc(all - (len - 2), x - 1, all) % MODULO)
        ) % MODULO
    ) % MODULO;
}

int main()
{
    int n, m; cin>>n>>m;
    cout<<calc(n, m, n)<<'\n';
}