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 <cstdio>

const int p = 1000000007;

int a[4000004];
int b[4000004];
int d[2002][2002];

int f(int x, int y) {
	return y ? y & 1 ? 1ll * f(x, y ^ 1) * x % p : f(1ll * x * x % p, y >> 1) : 1;
}

inline int nCr(int n, int r) {
	return n < r ? 0 : 1ll * a[n] * b[r] % p * b[n - r] % p;
}

int main() {
	int i, j, n, m;
	scanf("%d%d", &n, &m);
	if (m == 1) {
		puts("1");
		return 0;
	}
	a[0] = 1;
	for (i = 1; i <= n * m; i++) a[i] = 1ll * i * a[i - 1] % p;
	b[n * m] = f(a[n * m], p - 2);
	for (i = n * m; i >= 1; i--) b[i - 1] = 1ll * i * b[i] % p;
	d[0][0] = 1;
	for (i = 0; i <= n; i++) for (j = 0; j <= i; j++) {
		d[i + 1][j] = (d[i + 1][j] + d[i][j]) % p;
		if (j < i) d[i][j + 1] = (d[i][j + 1] + 1ll * d[i][j] * (n - j) % p * nCr((n - j) * m - i + j - 1, m - 2)) % p;
	}
	printf("%d", d[n][n]);
	return 0;
}