$n$개의 노드가 있으며, $i$번째 노드의 색깔은 $c_i$입니다. 주어진 정수 $k$ ($1 \le k \le n$)에 대하여, 다음 조건을 만족하도록 노드 사이에 정확히 $n-1$개의 무방향 간선을 만드는 방법의 수를 구하십시오.

(1) $n$개의 노드는 연결 그래프를 형성합니다. (2) 서로 다른 색깔의 노드를 연결하는 모든 간선을 제거하면, 남은 그래프의 각 연결 성분은 최대 $k$개의 정점을 가집니다.

두 가지 간선 구성 방법은 $1 \le i < j \le n$인 두 노드 $i$와 $j$ 사이에 한 방법에는 간선이 존재하고 다른 방법에는 존재하지 않는 경우가 하나라도 있을 때 서로 다르다고 간주합니다.

결과값이 클 수 있으므로, $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