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>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

typedef long long LL;
const int p=1000000007;
int n,m,fac[4000100],inv[4000100],f[2010][2010];

int calc(int n,int m)
{
    return LL(fac[n])*inv[m]%p*inv[n-m]%p;
}

int main()
{
    scanf("%d%d",&n,&m);
    if (m==1)
    {
        puts("1");
        return 0;
    }
    fac[0]=inv[0]=fac[1]=inv[1]=1;
    repu(i,2,n*m)
    {
        fac[i]=LL(fac[i-1])*i%p;
        inv[i]=LL(p-p/i)*inv[p%i]%p;
    }
    repu(i,2,n*m)
        inv[i]=LL(inv[i])*inv[i-1]%p;
    f[0][0]=1;
    repu(i,1,n)
        repu(j,0,i)
        {
            f[i][j]=f[i-1][j];
            if (j)
                f[i][j]=(f[i][j]+LL(f[i][j-1])*calc(n-i+(n-j+1)*(m-1)-1,m-2))%p;
        }
    printf("%d\n",LL(f[n][n])*fac[n]%p);
    return 0;
}