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<stdio.h>
long long Mod = 1000000007, Inv[4010000], F[4010000], InvF[4010000], D[2010][2010];
long long Comb(int a, int b){
    return F[a]*InvF[b]%Mod*InvF[a-b]%Mod;
}
int n, K;
int main(){
    int i, j;
    scanf("%d%d",&n,&K);
    if(K==1){
        printf("1\n");
        return 0;
    }
    Inv[1]=F[0]=InvF[0]=1;
    for(i=2;i<=n*K;i++){
        Inv[i] = Inv[Mod%i] * (Mod-Mod/i)%Mod;
    }
    for(i=1;i<=n*K;i++){
        F[i]=F[i-1]*i%Mod;
        InvF[i]=InvF[i-1]*Inv[i]%Mod;
    }
    for(i=0;i<=n;i++){
        for(j=i;j<=n;j++){
            if(i==0&&j==0)D[i][j]=1;
            if(i) D[i][j] = D[i-1][j];
            if(j>i) D[i][j] = (D[i][j] + D[i][j-1]* Comb(n*K - (n-i) - (n-j)*(K-1) - 1, K-2))%Mod;
        }
    }
    printf("%lld\n",D[n][n]*F[n]%Mod);
}