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 ; 
#define int long long 
const int MAXN = 2000 + 10 , MOD = 1e9+7 ; 

int n , k , dp[MAXN][MAXN] , fact[MAXN*MAXN] ,inv[MAXN*MAXN];

int pw(int a , int b)
{
	if(!b)
		return 1 ; 
	int res = pw(a , b/2) ; 
	res*=res ;
	res%=MOD ; 
	if(b%2)
		res*=a ; 
	return res%MOD ;  
}

int C(int a , int b)
{
	if(b>a)	
		return 0 ; 
	return ( (fact[a] * inv[b])%MOD ) *inv[a-b] %MOD ; 
}


int32_t main()
{
	cin >> n >> k ; 
	if(k==1)
		return cout << 1 , 0 ; 
	fact[0]=1 ; 
	for(int i=1 ; i<MAXN*MAXN ; i++)
		fact[i] = fact[i-1]*i %MOD ; 
	for(int i=0 ; i<MAXN*MAXN ; i++)
		inv[i] = pw(fact[i] , MOD-2) ;
	dp[n][n] = 1 ; 
	for(int i=n ; i>=0 ; i--)
	{
		for(int j=n ; j>=i ; j--)
		{
			if(i) 
				dp[i-1][j]=(dp[i-1][j] + dp[i][j])%MOD;
			if(j>i) 
				dp[i][j-1]= (dp[i][j-1] + dp[i][j]*(C(i+j*(k-1)-1,k-2))%MOD)%MOD;
		}
	}
	cout << (dp[0][0]*fact[n])%MOD << endl ; 
}