Problem: Snuke loves colorful balls. He has a total of N×K balls, K in each of his favorite N colors. The colors are numbered 1 through N.

He will arrange all of the balls in a row from left to right, in arbitrary order. Then, for each of the N colors, he will paint the leftmost ball of that color into color 0, a color different from any of the N original colors.

After painting, how many sequences of the colors of the balls are possible? Find this number modulo 10^9+7.

Constraints

* 1≤N,K≤2,000

Input

The input is given from Standard Input in the following format:


N K


Output

Print the number of the possible sequences of the colors of the balls after painting, modulo 10^9+7.

Examples

Input

2 2


Output

4


Input

3 1


Output

1


Input

2 3


Output

14


Input

2000 2000


Output

546381702

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for (int i = (a); i < (b); i++)
#define MOD 1000000007LL
#define N 2002
typedef long long ll;

int n, k;
ll dp[N][N], fct[N*N], inv[N*N], ifct[N*N];
int main() {
	scanf("%d %d", &n, &k);
	if (k==1) puts("1"), exit(0);
	fct[0] = 1;
	fo(i,1,N*N) fct[i] = (i * fct[i-1])%MOD;
	inv[1] = 1;
	fo(i,2,N*N) inv[i] = (-(MOD/i) * inv[MOD % i]) % MOD + MOD;
	ifct[0] = 1;
	fo(i,1,N*N) ifct[i] = (inv[i] * ifct[i-1])%MOD;
	dp[0][0] = 1;
	fo(i,0,n+1) fo(j,0,i+1) {
		dp[i+1][j] = (dp[i+1][j] + dp[i][j])%MOD;
		if (j < i) {
			int lft = n-i + (k-1)*(n - j - 1);
			dp[i][j+1] = (dp[i][j+1] + fct[lft + k-2] * (ifct[lft] * (ifct[k-2] * dp[i][j] % MOD)%MOD))%MOD;
		}
	}
	ll ans = (dp[n][n] * fct[n])%MOD;
	printf("%lld\n", ans);

	return 0;
}