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>
#define N 2005
#define LL long long
using namespace std;
const int mo=1e9+7;
int n,m,f[N][N],fc[N*N],xf[N*N];
LL fpm(LL x,LL y){ LL s=1; while(y){ if(y&1) s=(s*x)%mo; y>>=1,x=(x*x)%mo;} return s;}
LL C(int n,int m){ return 1LL*fc[n]*xf[m]%mo*xf[n-m]%mo;}
int main()
{
	int i,j;
	cin>>n>>m;
	if(m==1){ printf("1"); return 0;}
	f[0][0]=1;
	fc[0]=xf[0]=1;
	for(i=1;i<N*N;i++)
		fc[i]=(1LL*fc[i-1]*i)%mo;
	xf[N*N-1]=fpm(fc[N*N-1],mo-2);
	for(i=N*N-2;i>=0;i--)
		xf[i]=(1LL*xf[i+1]*(i+1))%mo;
	for(i=0;i<=n;i++)
		for(j=i;j<=n;j++){
			if(i<j) (f[i+1][j]+=f[i][j])%=mo;
			f[i][j+1]=(f[i][j+1]+f[i][j]*C(i-1+(m-1)*(j+1),m-2))%mo;
		  }
	printf("%lld\n",1LL*f[n][n]*fc[n]%mo);
	return 0;
}