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>
#include <iostream>
using namespace std;
const int mo = 1e9 + 7, N = 2e3 + 10, E = 5e6;
typedef long long ll;
ll f[N][N],jc[E],njc[E],suf[N][N];
ll n,k;
ll ksm(ll x,ll y) {
	ll ret = 1; for (; y; y>>=1) {if (y&1) ret = ret * x % mo;
		x = x * x % mo;
	}
	return ret;
}
ll C(ll x,ll y) {
	if (x < y) return 0;
	return jc[x] * njc[x-y] % mo * njc[y] % mo;
}
int main() {
	cin>>n>>k; if (k == 1) {
		printf("1"); return 0;
	}
	suf[0][0] = f[0][0] = 1;
	jc[0] = 1; for (int i = 1; i < E; i++) jc[i] = jc[i-1] * i % mo;
	njc[E-1] = ksm(jc[E - 1],mo-2);
	for (int i = E-2; ~i; i--) njc[i] = njc[i+1] * (i+1) % mo;
	for (int i = 1; i <= n; suf[i][0]=suf[i][1],i++) for (int j = i; j; j--) {
		f[i][j] = suf[i-1][j-1] * C(k+k*(i-1)-j-1,(i-1)*k-j+1) % mo;
		suf[i][j] = (suf[i][j+1] + f[i][j]) % mo;
	}
	printf("%lld\n",suf[n][1] * jc[n] % mo);
}