有 $n$ 個節點，其中第 $i$ 個節點的顏色為 $c_i$。給定一個整數 $k$ ($1 \le k \le n$)，請計算建立恰好 $n-1$ 條無向邊的方法數，使得：

(1) 這 $n$ 個節點形成一個連通圖。 (2) 如果我們移除所有連接不同顏色節點的邊，則剩餘圖中的每個連通分量最多包含 $k$ 個頂點。

若存在兩個節點 $i$ 和 $j$ ($1 \le i < j \le n$)，使得其中一種建邊方式包含連接 $i$ 與 $j$ 的邊，而另一種方式不包含，則這兩種建邊方式被視為不同。

由於答案可能很大，請輸出答案對 $10^9 + 7$ 取模後的結果。

輸入格式

第一行包含兩個整數 $n$ 和 $k$ ($1 \le k \le n \le 300$)。 接下來 $n$ 行包含整數 $c_1, c_2, \dots, c_n$，表示節點的顏色，每行一個整數 ($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