优美路径计数

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定 $n$ 个颜色为 $c_i$ 的瓷砖和整数 $k$。选择一个下标严格递增的子序列；若其长度是 $k$ 的倍数，且每连续 $k$ 个被选位置的颜色都相同，则称为优美路径。求最大长度优美路径的数量，对 $10^9+7$ 取模。

若无法选择完整的一组，则最大长度为零，空路径计为一种方案。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $n,k$，第二行包含 $c_1,\ldots,c_n$。

输出格式

对每组输出一个整数。

样例输入 1

5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5

样例输出 1

1
4
165
3
1

数据范围

• $1\le t\le10^4$，$1\le k\le n\le5000$，$1\le c_i\le n$；
• 所有测试组的 $n^2$ 之和不超过 $25\cdot10^6$。