Il y a $n$ nœuds, dont le $i$-ième a pour couleur $c_i$. Pour un entier donné $k$ ($1 \le k \le n$), veuillez compter le nombre de façons de construire exactement $n - 1$ arêtes non orientées entre les nœuds, de telle sorte que :

(1) Les $n$ nœuds forment un graphe connexe.

(2) Si nous détruisons chaque arête reliant deux nœuds de couleurs différentes, alors chaque composante connexe du graphe restant possède au plus $k$ sommets.

Deux façons de construire les arêtes sont considérées comme différentes si et seulement s'il existe deux nœuds $i$ et $j$ tels que $1 \le i < j \le n$ et qu'il existe une arête entre eux dans l'une des deux façons mais pas dans l'autre.

Comme le nombre peut être grand, vous devez seulement afficher la réponse modulo $10^9 + 7$.

Entrée

La première ligne contient deux entiers, $n$ et $k$ ($1 \le k \le n \le 300$).

Les $n$ lignes suivantes contiennent les entiers $c_1, c_2, \dots, c_n$ désignant les couleurs des nœuds, un entier par ligne ($1 \le c_i \le n$).

Sortie

Affichez la réponse modulo $10^9 + 7$.

Exemples

Entrée 1

5 3
1
1
3
1
5

Sortie 1

125

Entrée 2

4 2
2
1
1
1

Sortie 2

7