AtCoder Grand Contest 002

F - Leftmost Ball


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

12,...,N のボールがそれぞれ K 個ずつあります。 高橋君は、これら N×K 個のボールを好きな順番で横一列に並べました。 その後、各色ごとに最も左にあるボールを色 0 へ塗り替えました。

最終的なボールの色の並びは何通り考えられるでしょうか? 10^9+7 で割った余りを求めてください。

制約

  • 1≤N,K≤2,000

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

最終的なボールの色の並びは何通り考えられるか、10^9+7 で割った余りを出力せよ。


入力例1

2 2

出力例1

4

次の 4 通りです。

  • (0,1,0,2)
  • (0,0,1,2)
  • (0,2,0,1)
  • (0,0,2,1)

入力例2

3 1

出力例2

1

次の 1 通りです。

  • (0,0,0)

入力例3

2 3

出力例3

14

入力例4

2000 2000

出力例4

546381702

Problem Statement

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.


Sample Input 1

2 2

Sample Output 1

4

The following 4 sequences are possible:

  • (0,1,0,2)
  • (0,0,1,2)
  • (0,2,0,1)
  • (0,0,2,1)

Sample Input 2

3 1

Sample Output 2

1

The following 1 sequence is possible:

  • (0,0,0)

Sample Input 3

2 3

Sample Output 3

14

Sample Input 4

2000 2000

Sample Output 4

546381702

Submit提出する