Có $n$ nút, nút thứ $i$ có màu $c_i$. Với một số nguyên $k$ cho trước ($1 \le k \le n$), hãy đếm số cách xây dựng đúng $n - 1$ cạnh vô hướng giữa các nút sao cho:

(1) $n$ nút tạo thành một đồ thị liên thông.

(2) Nếu chúng ta loại bỏ mọi cạnh nối hai nút có màu khác nhau, thì mỗi thành phần liên thông trong đồ thị còn lại có tối đa $k$ đỉnh.

Hai cách xây dựng cạnh được coi là khác nhau khi và chỉ khi tồn tại hai nút $i$ và $j$ sao cho $1 \le i < j \le n$ và có một cạnh nối giữa chúng trong cách này nhưng không có trong cách kia.

Vì kết quả có thể rất lớn, bạn chỉ cần in ra đáp án theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \le k \le n \le 300$).

$n$ dòng tiếp theo chứa các số nguyên $c_1, c_2, \dots, c_n$ biểu thị màu của các nút, mỗi số trên một dòng ($1 \le c_i \le n$).

Dữ liệu ra

In ra đáp án theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

5 3
1
1
3
1
5

Dữ liệu ra 1

125

Dữ liệu vào 2

4 2
2
1
1
1

Dữ liệu ra 2

7