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

inputFormat

Input

The input is given from Standard Input in the following format:

N K

outputFormat

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

样例

2 3

14