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>
#define MN 2000
#define MOD 1000000007
int F[MN+5][MN+5],f[MN*MN+5],rf[MN*MN+5];
inline int inv(int x)
{
	int y=MOD-2,r=1;
	for(;y;y>>=1,x=1LL*x*x%MOD)if(y&1)r=1LL*r*x%MOD;
	return r;
}
inline int C(int n,int m){return 1LL*f[n]*rf[m]%MOD*rf[n-m]%MOD;}
int main()
{
	int n,k,i,j;
	scanf("%d%d",&n,&k);
	if(k<2)return 0*puts("1");
	for(f[0]=i=1;i<=n*k;++i)f[i]=1LL*f[i-1]*i%MOD;
	for(rf[i=n*k]=inv(f[n*k]);i--;)rf[i]=1LL*rf[i+1]*(i+1)%MOD;
	for(F[0][0]=1,i=0;i<=n;++i)for(j=0;j<=i;++j)
	{
		if(i<n)F[i+1][j]=(F[i+1][j]+F[i][j])%MOD;
		if(j<i)F[i][j+1]=(F[i][j+1]+1LL*F[i][j]*(n-j)%MOD*C((n-j-1)*(k-1)+n-i+k-2,k-2))%MOD;
	}
	printf("%d",F[n][n]);
}