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<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;

ll minv[4000001];
ll C[4000001];
int N,K;

ll dp[2001][2001];
ll back(ll i, ll j){
    ll &ret = dp[i][j];
    if(ret) return ret;
    if(i==0&&j==0) return ret=1;

    if(i) ret += back(i-1,j);
    if(j>i) ret += back(i,j-1)*C[i+j*(K-1)-1]%MOD;
    return ret %= MOD;
}

int main(){
    scanf("%d%d",&N,&K);

    minv[1] = 1;
    for(int i=2;i<=N*K;i++){
        minv[i] = MOD - (MOD/i)*minv[MOD%i]%MOD;
    }

    C[K-2] = 1;
    for(int i=K-1;i<=N*K;i++){
        C[i] = C[i-1]*i%MOD*minv[i-(K-2)]%MOD;
    }

    if(K==1) printf("1");
    else{
        ll ans = back(N,N);
        for(int i=1;i<=N;i++) ans=ans*i%MOD;
        printf("%lld",ans);
    }
}