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<iostream>
#include<algorithm>
#include<vector>
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N 2010
#define M 5000010
class Comb{
  public:
  ll fac[M],inv[M],ivf[M];
  void init(){
    fac[0]=ivf[0]=inv[1]=1;
    for(ll i=1;i<M;i++){
      if(i>1)inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;
      fac[i]=fac[i-1]*i%mod;
      ivf[i]=ivf[i-1]*inv[i]%mod;
    }
  }
  ll qry(ll n,ll k){
    return fac[n]*ivf[n-k]%mod*ivf[k]%mod;
  }
};Comb C;
ll f[N][N],n,k;
int main(){
    C.init();
    cin>>n>>k;
    if(k==1){cout<<1<<endl; return 0;}
    for(ll i=0;i<N;i++)for(ll j=0;j<N;j++)f[i][j]=0; f[0][0]=1;
    for(ll x=0;x<N;x++)for(ll y=0;y<N;y++){
      if(x+1<=y){
	f[x+1][y]=(f[x+1][y]+f[x][y])%mod;
      }
      if(y+1<=n){
	f[x][y+1]=(f[x][y+1]+f[x][y]*C.qry(x+y*(k-1)+k-2,k-2))%mod;
      }
    }
    cout<<f[n][n]*C.fac[n]%mod<<endl;
    return 0;
}