

Time Limit: 2 sec / Memory Limit: 256 MB
問題文
色 1,2,...,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