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;
const int maxn=2000*2000,p=1e9+7;
int fac[maxn+9],ifac[maxn+9];
inline int poww(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1ll*a*ans%p;b>>=1;
		a=1ll*a*a%p;
	}return ans;
}
int C(int n,int m){
	if(n<m)return 0;
	return 1ll*fac[n]*ifac[m]%p*ifac[n-m]%p;
} 
void init(){
	int inv2=p-(p/2);
	fac[0]=1;for(int i=1;i<=maxn;++i)fac[i]=1ll*fac[i-1]*i%p;
	ifac[maxn]=poww(fac[maxn],p-2);for(int i=maxn-1;i>=0;--i)ifac[i]=1ll*(i+1)*ifac[i+1]%p;
}
int n,k,f[2020][2020];
int main(){
	init();
	cin>>n>>k;
	if(k==1){cout<<1;return 0;}
	for(int i=1;i<=n;++i)f[i][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j){
			f[i][j]=f[i-1][j];
			f[i][j]=(f[i][j]+1ll*f[i][j-1]*(n-j+1)%p*C(n*k-i-(j-1)*(k-1)-1,k-2)%p)%p;
		}
	cout<<f[n][n];
}