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

using namespace std;

long long n,m,r,pw,mod=1000000007;
long long dp[3001][3001];

int main()
{
	scanf("%lld%lld",&n,&m);
	
	dp[1][1]=m;
	for(long long j=1;j<=min(m,n);j++)
	{
		long long p=0;
		for(long long i=2;i<n;i++)
		{
			dp[i][j]=(dp[i-1][j]*(m-j)+p*(m-j+1))%mod;
			p=((p+dp[i-1][j-1])*(j-1))%mod;
		}
		pw=j;
		for(long long i=n-1;i;i--)
		{
			r=(r+dp[i][j]*pw)%mod;
			pw=(pw*j)%mod;
		}
	}

	printf("%lld\n",r);

	return 0;
}