p04038 AtCoder Grand Contest 002 - Leftmost Ball
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
```python
def pow_mod(MOD, a, n):
    ret = 1
    while n != 0:
        if n % 2 == 1: ret = ret * a % MOD
        a = a * a % MOD
        n //= 2
    return ret

def fac(n):
    MOD = 1000000007
    ret = 1
    for i in range(1, n + 1):
        ret = ret * i % MOD
    return ret

def fac_gen(first, last):
    MOD = 1000000007
    ret = fac(first)
    yield ret
    for i in range(first + 1, last):
        ret = ret * i % MOD
        yield ret

def build_comb_list(f, m, K):
    MOD = 1000000007
    v = pow_mod(MOD, f[m - K * 2] * f[0], MOD - 2)
    for i in range(m - K, -1, -1):
        f[i] *= v
        v = v * i % MOD

def solve_dp(n, k, comb):
    MOD = 1000000007
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        ci = (i - 1) * (k - 1)
        v = 0
        for j, c in zip(range(i), comb[ci:ci + i]):
            v = (v + dp[j] * c) % MOD
            dp[j] = v
        dp[i] = v
    return dp[n] * fac(n) % MOD

def solve(n, k):
    if n == 1 or k == 1: return 1
    m = n * k
    comb = list(fac_gen(k - 2, m - 1))
    build_comb_list(comb, m - 2, k - 2)
    return solve_dp(n, k, comb)


n, k = (int(s) for s in input().split(' '))
print(solve(n, k))

```