Colorful Components

시간 제한2초메모리 제한512 MB

요약

n개 정점에 색이 주어질 때, 서로 다른 색을 잇는 간선을 지운 뒤 남는 같은 색 성분의 크기가 모두 k 이하가 되도록 하는 연결 그래프(라벨 트리)의 개수를 세는 문제다.

문제

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

두 간선 구성이 서로 다른 것은, $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, \ldots, c_n$ 이 한 줄에 하나씩 주어진다( $1 \le c_i \le n$ ).

답을 $10^9 + 7$ 로 나눈 나머지를 출력한다.