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>
using namespace std ;
#define int unsigned long long
const int mxn = 8000005 ;
const int Mod = 1e9+7 ;
int frac[mxn], inv[mxn];
int f[2005][2005], n, k;
int power(int a, int b){
    int res=1, car=a; 
    while(b){
        if(b&1) (res*=car)%=Mod;
        (car*=car)%=Mod;
        b>>=1;
    }
    return res;
}
void init(){
    frac[0]=1 ;
    for(int i=1;i<mxn;++i) (frac[i]=frac[i-1]*i)%=Mod ;
    inv[mxn-1] = power(frac[mxn-1], Mod-2);
    for(int i=mxn-2;i>0;--i) inv[i]=(inv[i+1]*(i+1))%Mod ;
    inv[0] = 1 ;
}
int C(int n, int k){
    return ((frac[n]*inv[k]%Mod)*inv[n-k])%Mod ;
}
signed main(){
    init() ;
    cin>>n>>k;
    if(k==1) return puts("1"),0 ;
    f[0][0] = 1 ;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=i;++j)
            (f[i][j] = f[i-1][j]+(j?((((f[i][j-1]*(n-j+1))%Mod)*C(n*k-i-(j-1)*(k-1)-1, k-2))%Mod):(0)))%=Mod ;
    cout<<f[n][n]<<endl ;
}