$n$ 個のノードがあり、$i$ 番目のノードは色 $c_i$ を持っています。与えられた整数 $k$ ($1 \le k \le n$) に対して、以下の条件を満たすようにノード間にちょうど $n-1$ 本の無向辺を張る方法の数を数えてください。

(1) $n$ 個のノードが連結グラフを形成すること。 (2) 異なる色のノードを結ぶすべての辺を取り除いたとき、残りのグラフの各連結成分の頂点数が高々 $k$ 個であること。

2 つの辺の張り方は、ある 2 つのノード $i$ と $j$ ($1 \le i < j \le n$) が存在し、一方の張り方ではその間に辺があり、もう一方の張り方では辺がない場合にのみ、異なるものとみなします。

答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

入力は以下の形式で与えられます。

$n$ $k$ $c_1$ $c_2$ $\vdots$ $c_n$

ここで、$n$ と $k$ は $1 \le k \le n \le 300$ を満たす整数であり、$c_i$ は $1 \le c_i \le n$ を満たすノードの色を表す整数です。

出力

答えを $10^9 + 7$ で割った余りを出力してください。

入出力例

入力 1

5 3
1
1
3
1
5

出力 1

125

入力 2

4 2
2
1
1
1

出力 2

7