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
64
65
66
67
68
69
70
71
72
73
#include <cstdio>

typedef long long int lld;
#define P 1000000007

/*
lld phi(lld n,lld m)
{
lld r = m,i;
	if (n == 0) return 1;
	if (n == 1) return m;
	else
	{
		for (i = 2; i < n; i++)
		{
			r *= m-1;
			r %= P;
		}
		return r;
	}
}

lld f(lld n,lld m)
{
lld r = 0,i;
	if (n == 0) return 1;
	if (n == 1) return m;
	else
	{
		for (i = 0; i < n-1; i++)
		{
//printf("phi(%lld,%lld) = %lld, f(%lld,%lld) = %lld\n",n-i,m,phi(n-i,m),i,m,f(i,m));
			r += phi(n-i,m)*f(i,m);
			r %= P;
		}
		return r;
	}
}
*/

int main()
{
lld N,M,i,j;
lld phi[3000+1],f[3000+1];

	scanf("%lld %lld",&N,&M);
	
	phi[0] = 0;
	phi[1] = M;
	phi[2] = M;
	for (i = 3; i < N+1; i++) phi[i] = (phi[i-1] * (M-1)) % P;
	
//	for (i = 0; i <= N; i++) printf("%lld\n",phi[i]);
	

	f[0] = 1;
	f[1] = M;
	for (i = 2; i < N+1; i++)
	{
		f[i] = 0;
		for (j = 0; j < i-1; j++)
		{
			f[i] += (phi[i-j] * f[j]) % P;
//printf("%lld %lld %lld %lld\n",i,j,phi[i-j],f[j]);
		}
		f[i] %= P;
	}
//	for (i = 0; i < N+1; i++) printf("%lld\n",f[i]);

	printf("%lld\n",f[N]);
	
	return 0;
}