Mamy $n$ wierzchołków, z których $i$-ty ma kolor $c_i$. Dla danej liczby całkowitej $k$ ($1 \le k \le n$), oblicz liczbę sposobów na zbudowanie dokładnie $n-1$ nieskierowanych krawędzi między wierzchołkami, tak aby:

(1) $n$ wierzchołków tworzyło graf spójny. (2) Jeśli usuniemy każdą krawędź łączącą dwa wierzchołki różnych kolorów, to każda składowa spójna w pozostałym grafie będzie miała co najwyżej $k$ wierzchołków.

Dwa sposoby budowania krawędzi uznaje się za różne wtedy i tylko wtedy, gdy istnieją dwa wierzchołki $i$ oraz $j$ takie, że $1 \le i < j \le n$ oraz istnieje krawędź między nimi w jednym ze sposobów, a w drugim nie.

Ponieważ liczba ta może być duża, należy wypisać wynik modulo $10^9 + 7$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le k \le n \le 300$).

Kolejne $n$ linii zawiera liczby całkowite $c_1, c_2, \dots, c_n$ oznaczające kolory wierzchołków, po jednej liczbie w linii ($1 \le c_i \le n$).

Wyjście

Wypisz wynik modulo $10^9 + 7$.

Przykład

Wejście 1

5 3
1
1
3
1
5

Wyjście 1

125

Wejście 2

4 2
2
1
1
1

Wyjście 2

7