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 N=2002,M=1e9+7;
int n,m,k,f[N*N],F[N*N],g[N][N];
int mi(int a,int b){
	int s=1;
	for(;b;b>>=1,a=1LL*a*a%M)if(b&1)s=1LL*s*a%M;
	return s;
}
int main(){
	cin>>n>>k;m=n*k;
	if(k==1){puts("1");return 0;}
	f[0]=1;
	for(int i=1;i<=m;++i)f[i]=1LL*f[i-1]*i%M;
	F[m]=mi(f[m],M-2);
	for(int i=m;i>=1;--i)F[i-1]=1LL*F[i]*i%M;
	g[0][0]=1;
	for(int i=0,I=k-1;i<=n;++i,I+=k-1)for(int j=0;j<=i;++j){
		(g[i+1][j]+=1LL*g[i][j]*f[I+j-1]%M*F[I+j-k+1]%M*F[k-2]%M)%=M;
		(g[i][j+1]+=g[i][j])%=M;
	}
	cout<<1LL*g[n][n]*f[n]%M<<endl;
}