AT_tenka1_2013_final_d 天下一ボディービルコンテスト

[problemUrl]: https://atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_d 高橋君は、頭には自信がありませんが、体には自信があります。そこで、高橋君はボディービルコンテストに出ることにしました。 高橋君には筋肉が $ N $ 個ついています。 高橋君は、ボディービルコンテストが開かれるまでの $ D $ 日間、毎日トレーニングをすることにしました。 高橋君は、毎日筋肉をひとつ選び、トレーニングしてその筋肉を $ 1 $kg 増やします。 高橋君は、ボディービルコンテストで優勝するために、各筋肉をどれだけ増やすか、目標を設定しました。ですが、その目標を達成するために、どのようなスケジュールでトレーニングをすれば良いかが分かりません。 高橋君のために、トレーニングスケジュールが何通りあるかを、mod $ 1000000007 $で求めてください。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ - $ 1 $ 行目は、高橋君の筋肉の数 $ N $ ($ 1\ \leq\ N\ \leq\ 30 $) と トレーニング日数 $ D $ ($ 1\ \leq\ D\ \leq\ 10^9 $) が空白区切りで与えられる。 - $ 2 $ 行目から $ N+1 $ 行目までの $ N $ 行は、$ i $ ($ 1\ \leq\ i\ \leq\ N $) 番目の筋肉を最低何kg増やしたいかの目標 $ a_i\ (1\ \leq\ a_i\ \leq\ 30) $ が与えられる。 - $ N\ \leq\ 5,\ a_i\ \leq\ 5,\ D\ \leq\ 500 $ の入力に正解すると、$ 280 $ 点満点に対して部分点として、$ 40 $ 点が与えられる。 - $ N\ \leq\ 5,\ a_i\ \leq\ 5 $ の入力に正解すると、$ 280 $ 点満点に対して部分点として、上記とは別に $ 100 $ 点が与えられる。 高橋君が全ての目標を達成するための、スケジュールの組み方が何通りあるかを、$ 1000000007 $ で割った余りを出力しなさい。 また、出力の最後には改行をいれること。 ``` 2 3 1 1 ``` ``` 6 ``` 鍛えるべき筋肉が$ 2 $つあり、$ 3 $日間トレーニングします。 スケジュールの組み方は、1日目から順番に、{1,1,2}, {1,2,1}, {1,2,2}, {2,1,1}, {2,1,2}, {2,2,1}の$ 6 $通りです。 ``` 4 4 1 1 1 1 ``` ``` 24 ``` 鍛えるべき筋肉が$ 4 $つあり、$ 4 $日間のトレーニングでそれぞれ$ 1 $つの筋肉を選ぶ必要があり、その組み合わせは$ 4!=24 $通りです。 ``` 13 12345678 1 2 3 4 5 6 7 8 9 10 11 12 13 ``` ``` 910759485 ```

N/A

N/A