/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は幼稚園の先生です。高橋君は N 人の児童にちょうど K 個のキャンディを配り切ることにしました。
ここで、全体の幸福度を、各児童が貰ったキャンディの個数の積として定義します。
高橋君は N 人の児童にキャンディを配り切ったときの、全体の幸福度を最大化したいと思っています。 全体の幸福度を最大化するようなキャンディの分配方法が何通りあるかを数えてください。答えは大きくなる可能性があるので答えを 1,000,000,007(10^9+7) で割った余りを出力してください。
各児童に配られたキャンディの個数が 1 つでも異なっていれば、配り方は区別されます。児童は区別され、キャンディは区別されません。また、定義からキャンディを 1 つも貰えない児童が 1 人でもいると、全体の幸福度は 0 になることに気をつけてください。
入力
入力は以下の形式で標準入力から与えられる。
N K
- 1 行目には、児童の数とキャンディの数を表す 2 つの整数 N (1 ≦ N ≦ 100) と K (1 ≦K ≦ 500) が空白区切りで与えられる。
部分点
この問題には部分点が設定されている。
- 80 点分のテストケースでは、 問題文の制約に加え、さらに N≦K を満たす。
- 残りの 20 点分のテストケースに追加の制約はない。
出力
出力は以下の形式で標準出力に行うこと。
1 行目に、求める答えを 1,000,000,007 で割った余りを出力せよ。
末尾の改行を忘れないこと。
入力例1
4 10
出力例1
6
4 人の児童のうち、2 人にキャンディを 3 個ずつ、残りの 2 人にキャンディを 2 個ずつ配ると、全体の幸福度が 3×3×2×2=36 となり、またこの時最大値を達成しています。
そのような配り方は、4 人の児童に配られたキャンディの数を c_1,c_2,c_3,c_4 とすると、(c_1,c_2,c_3,c_4) が
- (3,3,2,2)
- (3,2,3,2)
- (3,2,2,3)
- (2,3,3,2)
- (2,3,2,3)
- (2,2,3,3)
となるような配り方であり、6 通り存在します。
入力例2
100 450
出力例2
538992043
出力するものは、本来の答えを 1,000,000,007 で割った余りだということに気をつけてください。
入力例3
5 2
出力例3
15
どうキャンディを配っても全体の幸福度が 0 になるので、どう配っても良いです。