D - 天下一ボディービルコンテスト Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、頭には自信がありませんが、体には自信があります。そこで、高橋君はボディービルコンテストに出ることにしました。

高橋君には筋肉が N 個ついています。 高橋君は、ボディービルコンテストが開かれるまでの D 日間、毎日トレーニングをすることにしました。

高橋君は、毎日筋肉をひとつ選び、トレーニングしてその筋肉を 1kg 増やします。

高橋君は、ボディービルコンテストで優勝するために、各筋肉をどれだけ増やすか、目標を設定しました。ですが、その目標を達成するために、どのようなスケジュールでトレーニングをすれば良いかが分かりません。

高橋君のために、トレーニングスケジュールが何通りあるかを、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 で割った余りを出力しなさい。

また、出力の最後には改行をいれること。

入力例 1

2 3
1
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通りです。

入力例 2

4 4
1
1
1
1

出力例 2

24

鍛えるべき筋肉が4つあり、4日間のトレーニングでそれぞれ1つの筋肉を選ぶ必要があり、その組み合わせは4!=24通りです。

入力例 3

13 12345678
1
2
3
4
5
6
7
8
9
10
11
12
13

出力例 3

910759485