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 il inline
#define RG register
#define ll long long
#define rhl (1000000007)
#define N (5000010)

using namespace std;

int fac[N],ifac[N],inv[N];
int f[2010][2010],n,k;

il int C(RG int n,RG int m){
  return 1LL*fac[n]*ifac[m]%rhl*ifac[n-m]%rhl;
}

il void add(RG int &x,RG int v){
  x+=v; if (x>=rhl) x-=rhl; return;
}

int main(){
  cin>>n>>k;
  if (k==1) puts("1"),exit(0); f[0][0]=fac[0]=ifac[0]=1;
  for (RG int i=1;i<=(n+1)*k;++i){
    inv[i]=i==1 ? 1 : 1LL*(rhl-rhl/i)*inv[rhl%i]%rhl;
    fac[i]=1LL*fac[i-1]*i%rhl,ifac[i]=1LL*ifac[i-1]*inv[i]%rhl;
  }
  for (RG int i=0;i<=n;++i)
    for (RG int j=0;j<=n;++j){
      if (i<j) add(f[i+1][j],f[i][j]);
      add(f[i][j+1],1LL*f[i][j]*C(i+(j+1)*(k-1)-1,k-2)%rhl);
    }
  cout<<1LL*f[n][n]*fac[n]%rhl; return 0;
}