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;
typedef long long ll;

const ll p = 1e9+7;
const int M = 2005;

ll fact[M*M], invfact[M*M], inv[M*M], dp[M][M], part[M][M], n, k;

ll comb(int x, int y) {
	if (x < 0 || y < 0 || x < y)
		return 0;
	return fact[x]*invfact[y]%p*invfact[x-y]%p;
}

int main() {
	cin >> n >> k;
	if (k == 1) {
		cout << "1\n"; return 0;
	}
	inv[1] = fact[0] = fact[1] = invfact[0] = invfact[1] = 1;
	for (int i = 2; i < M*M; ++i) {
		inv[i] = (p - (p/i) * inv[p%i] % p) % p;
		fact[i] = i*fact[i-1]%p;
		invfact[i] = inv[i]*invfact[i-1]%p;
	}

	for (int i = 1; i <= n; ++i) {
		// casework on longest prefix of 0s
		if (i == 1)
			dp[i][1] = 1;
		else
			for (int j = 1; j <= i; ++j)
				dp[i][j] = comb(i*k-j-1, k-2)*i%p*part[i-1][j-1]%p;
		
		for (int j = i; j >= 0; --j)
			part[i][j] = (part[i][j+1]+dp[i][j])%p;
	}

	cout << part[n][0] << endl;
}