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;
typedef pair<int, int> P;
template<typename T> inline void chkmin(T &a, const T &b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T &a, const T &b) { a = a > b ? a : b; }

const int MAXN = 2005, MAXM = 4000005, MOD = 1e9 + 7;
int f[MAXN][MAXN], g[MAXM], inv[MAXM], n, K;

int main() {
	scanf("%d%d", &n, &K);
	if (K == 1) return puts("1") * 0;
	inv[1] = 1;
	for (int i = 2; i <= n * K; i++)
		inv[i] = MOD - (LL)MOD / i * inv[MOD % i] % MOD;
	g[K - 2] = 1;
	for (int i = K - 1; i <= n * K; i++)
		g[i] = (LL)g[i - 1] * i % MOD * inv[i - K + 2] % MOD;
	f[n][n] = 1;
	for (int i = n - 1; i >= 0; i--)
	for (int j = n; j >= i; j--)
		f[i][j] = (f[i + 1][j] + (LL)f[i][j + 1] * g[i + (K - 1) * (j + 1) - 1] % MOD * (j + 1)) % MOD;
	printf("%d\n", f[0][0]);
	return 0;
}