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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <set>

using namespace std;

typedef long long ll;
const ll MODULO = 1000 * 1000 * 1000 + 7;

#define MAXN 3000

ll a[MAXN+10];
ll b[MAXN+10];

ll inverse_modulo(ll a, ll m) {
	ll s = 0, prev_s = 1, q, mod = m;
	while (m != 0) {
		q = a / m;
		a = a - q*m;
		swap(a, m);
		prev_s = prev_s - q*s;
		swap(s, prev_s);
	}
	return prev_s >= 0 ? prev_s : prev_s + mod;
}

int main(){
	ll n, m, mpowi_minus1, inv, tmp;
	scanf("%lld%lld", &n, &m);
	mpowi_minus1 = m;
	inv = inverse_modulo(m, MODULO);
	a[0] = b[0] = 1;
	a[1] = b[1] = 0;
	a[2] = b[2] = m;
	for (int i = 3; i <= n; ++i) {
		mpowi_minus1 *= m;
		mpowi_minus1 %= MODULO;
		b[i] = mpowi_minus1;
		for (int j = 2; j <= i-2; ++j) {
			a[i] += (b[j]*a[i-j]) % MODULO;
		}
		for (int k = 2; k <= i-2; ++k) {//TODO: <= i-4? -3?
			for (int j = k+1; j <= i-2;++j) {
				//tmp = (b[j-2]* a[i-j]) % MODULO ;
				//tmp = (b[k+1]* a[i-k-1]) % MODULO ;
				tmp = (b[k]* a[i-j]) % MODULO ;
				tmp *= j-k == 0 ? 1 : b[j-k-2];
				tmp %= MODULO;
				//if (j == k+1)
				//	tmp = (tmp * inv) %MODULO;
				a[i] -= tmp;
				a[i] = (a[i] + MODULO) % MODULO;
			}
		}
		//if (i >= 5) {
		//	a[i] -= ((a[i-3]) *(i-4)) % MODULO;
		//	a[i] = (a[i] + MODULO) % MODULO;
		//}
		a[i] = (b[i] + a[i]) % MODULO - (a[i]*inv) % MODULO;
		a[i] = (a[i] + MODULO) % MODULO;
	}
	printf("%lld\n", a[n]);
	return 0;
}