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
#include <stdio.h>

#define mod 1000000007
#define llmul(a, b) ((long long)(a) * (b))

int g[3001][3001];
int b[3001][3001];

int main(void)
{
	int n, m;
	int ans = 0;
	int i, j;

	scanf("%d%d", &n, &m);
	g[0][0] = 1;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= i; j++) {
			g[i][j] = llmul(j, g[i-1][j] + b[i-1][j]) % mod;
			b[i][j] = (llmul(m-j+1, g[i-1][j-1]) + llmul(m-j, b[i-1][j])) % mod;
		}
	}
	for (j = 0; j <= n; j++)
		ans = (ans + g[n][j]) % mod;
	printf("%d\n", ans);

	return 0;
}