有 $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