21115번 - Colorful Components 다국어

문제

There are $n$ nodes, the $i$-th of which has color $c_i$. For a given integer $k$ (1ドル \le k \le n$), please count the number of ways to build exactly $n - 1$ undirected edges between the nodes, such that:

1. The $n$ nodes form a connected graph.
2. If we destroy every edge that connects two nodes of different colors, then every connected component in the remaining graph has at most $k$ vertices.

Two ways of building edges are considered different if and only if there exist two nodes $i$ and $j$ such that 1ドル \le i < j \le n$ and there is an edge between them in one of the two ways but not in the other.

Since the number could be large, you only need to output the answer modulo 10ドル^9 + 7$.

입력

The first line contains two integers, $n$ and $k$ (1ドル \le k \le n \le 300$).

The following $n$ lines contain integers $c_1, c_2, \ldots, c_n$ denoting the colors of the nodes, one integer per line (1ドル \le c_i \le n$).

출력

Output the answer modulo 10ドル^9 + 7$.

제한

힌트