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:
/*只要保证这个颜色开始的第一个填在第一个空位上
之后的都随便填即可
所以方案数就是C(空格位置-1,数量-1),组合意义就是开始的第一个颜色只有一个位置能填*/
#include<bits/stdc++.h>
#define Mod 1000000007
#define N 2005
#define M N*N
using namespace std;
int n,K,dp[N][N],fac[M],inv[M];
inline int ksm(int x,int y){
	int ans1=1;while (y){
		if (y&1) ans1=1ll*ans1*x%Mod;
		y>>=1;x=1ll*x*x%Mod;
	}return ans1;
}
inline int C(int n,int m){return 1ll*fac[n]*inv[m]%Mod*inv[n-m]%Mod;}
int main(){
	scanf("%d%d",&n,&K);
	if (K==1) return puts("1"),0;dp[0][0]=1;
	fac[0]=1;for (int i=1;i<M;i++) fac[i]=1ll*fac[i-1]*i%Mod;
	inv[M-1]=ksm(fac[M-1],Mod-2);
	for (int i=M-2;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=i;j++){
			if (i) dp[i][j]=1ll*(dp[i][j]+dp[i-1][j])%Mod;
			if (j) dp[i][j]=1ll*(1ll*dp[i][j-1]*C(n*K-i-(j-1)*(K-1)-1,K-2)%Mod+dp[i][j])%Mod;
		}
	}
	printf("%lld\n",1ll*dp[n][n]*fac[n]%Mod);
	return 0;
}