Имеется $n$ узлов, $i$-й из которых имеет цвет $c_i$. Для заданного целого числа $k$ ($1 \le k \le n$) подсчитайте количество способов построить ровно $n - 1$ неориентированное ребро между узлами так, чтобы:

(1) $n$ узлов образовывали связный граф.

(2) Если удалить все ребра, соединяющие узлы разных цветов, то каждая компонента связности в оставшемся графе будет содержать не более $k$ вершин.

Два способа построения ребер считаются различными тогда и только тогда, когда существуют два узла $i$ и $j$ ($1 \le i < j \le n$), такие что в одном способе между ними есть ребро, а в другом — нет.

Поскольку число может быть очень большим, выведите ответ по модулю $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