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

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

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

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

高橋君のために、トレーニングスケジュールが何通りあるかを、mod $1000000007$で求めてください。

• $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