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>
#define C(n,m) (1ll*ml[n]*ny[m]%mo*ny[(n)-(m)]%mo)
#define cal(a,b) ((a+=b)%=mo)
using namespace std;
const int mo=1e9+7;
int f[2050][2050],ml[4000050],ny[4000050];
int fap(int a,int b){
  int s=1;
  while(b){
    if (b&1) s=1ll*a*s%mo;
    b>>=1,a=1ll*a*a%mo;
  }
  return s;
}
int main(){
  int n,k; cin>>n>>k;
  if (k==1) return puts("1"),0;
  ml[0]=ny[0]=1;
  for (int i=1; i<=n*k; ++i) ml[i]=1ll*ml[i-1]*i%mo;
  ny[n*k]=fap(ml[n*k],mo-2);
  for (int i=n*k-1; i; --i) ny[i]=1ll*(i+1)*ny[i+1]%mo;
  f[0][0]=1;
  for (int i=0; i<n; ++i)
    for (int j=0; j<=i; ++j){
      cal(f[i+1][j],1ll*f[i][j]*C((i+1)*(k-1)+j-1,k-2)%mo);
      if (j!=i) cal(f[i][j+1],f[i][j]);
    }
  for (int i=0; i<n; ++i) cal(f[n][i+1],f[n][i]);
  for (int i=1; i<=n; ++i) f[n][n]=1ll*f[n][n]*i%mo;
  cout<<f[n][n];
  return 0;
}