Hay $n$ nodos, donde el $i$-ésimo tiene color $c_i$. Para un entero dado $k$ ($1 \le k \le n$), por favor cuente el número de formas de construir exactamente $n - 1$ aristas no dirigidas entre los nodos, tales que:

(1) Los $n$ nodos formen un grafo conexo.

(2) Si destruimos cada arista que conecta dos nodos de diferentes colores, entonces cada componente conexa en el grafo restante tenga como máximo $k$ vértices.

Dos formas de construir aristas se consideran diferentes si y solo si existen dos nodos $i$ y $j$ tales que $1 \le i < j \le n$ y existe una arista entre ellos en una de las dos formas pero no en la otra.

Dado que el número puede ser grande, solo necesita imprimir la respuesta módulo $10^9 + 7$.

Entrada

La primera línea contiene dos enteros, $n$ y $k$ ($1 \le k \le n \le 300$).

Las siguientes $n$ líneas contienen los enteros $c_1, c_2, \dots, c_n$ que denotan los colores de los nodos, un entero por línea ($1 \le c_i \le n$).

Salida

Imprima la respuesta módulo $10^9 + 7$.

Ejemplos

Entrada 1

5 3
1
1
3
1
5

Salida 1

125

Entrada 2

4 2
2
1
1
1

Salida 2

7