310301: CF1811G2. Vlad and the Nice Paths (hard version)

G2. Vlad and the Nice Paths (hard version)time limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

This is hard version of the problem, it differs from the easy one only by constraints on $n$ and $k$.

Vlad found a row of $n$ tiles and the integer $k$. The tiles are indexed from left to right and the $i$-th tile has the color $c_i$. After a little thought, he decided what to do with it.

You can start from any tile and jump to any number of tiles right, forming the path $p$. Let's call the path $p$ of length $m$ nice if:

• $p$ can be divided into blocks of length exactly $k$, that is, $m$ is divisible by $k$;
• $c_{p_1} = c_{p_2} = \ldots = c_{p_k}$;
• $c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$;
• $\ldots$
• $c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$;

Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $10^9 + 7$.

Input

The first line of each test contains the integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 5000$) — the number of tiles in a row and the length of the block.

The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le n$) — tile colors.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $25 \cdot 10^6$.

Output

Print $t$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $10^9 + 7$.

ExampleInput

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

Output

1
4
165
3
1

Note

In the first sample, it is impossible to make a nice path with a length greater than $0$.

In the second sample, we are interested in the following paths:

• $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$
• $2 \rightarrow 4 \rightarrow 5 \rightarrow 7$
• $1 \rightarrow 3 \rightarrow 5 \rightarrow 7$
• $1 \rightarrow 3 \rightarrow 4 \rightarrow 7$

In the third example, any path of length $8$ is nice.

题目大意：
这是一个难题的版本，与简单版本的区别仅在于对n和k的限制。

Vlad找到了一排n个瓦片和整数k。瓦片从左到右编号，第i个瓦片的颜色为c_i。他决定对它进行处理。

可以从任一瓦片开始，向右跳任意数量的瓦片，形成路径p。如果满足以下条件，则称长度为m的路径p为“好”路径：

- p可以划分为长度恰好为k的块，即m能被k整除；
- c_{p_1} = c_{p_2} = … = c_{p_k}；
- c_{p_{k+1}} = c_{p_{k+2}} = … = c_{p_{2k}}；
- …
- c_{p_{m-k+1}} = c_{p_{m-k+2}} = … = c_{p_{m}}；

任务是找到最大长度的“好”路径的数量。由于这个数字可能太大，所以输出对10^9 + 7取模的结果。

输入数据格式：
每个测试的第一行包含整数t（1≤t≤10^4）——测试用例的数量。

每个测试用例的第一行包含两个整数n和k（1≤k≤n≤5000）——一排瓦片的数量和块长度。

每个测试用例的第二行包含n个整数c_1, c_2, c_3, …, c_n（1≤c_i≤n）——瓦片颜色。

保证所有测试用例的n^2之和不超过25 * 10^6。

输出数据格式：
输出t个数，每个数是对应测试用例的答案——最大长度的“好”路径数量对10^9 + 7取模的结果。

示例输入输出：
```
Input
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
Output
1
4
165
3
1
```
注意：
在第一个示例中，无法制作长度大于0的“好”路径。
在第二个示例中，我们关注以下路径：
- 1 → 3 → 4 → 5
- 2 → 4 → 5 → 7
- 1 → 3 → 5 → 7
- 1 → 3 → 4 → 7
在第三个示例中，任何长度为8的路径都是“好”路径。题目大意： 这是一个难题的版本，与简单版本的区别仅在于对n和k的限制。 Vlad找到了一排n个瓦片和整数k。瓦片从左到右编号，第i个瓦片的颜色为c_i。他决定对它进行处理。 可以从任一瓦片开始，向右跳任意数量的瓦片，形成路径p。如果满足以下条件，则称长度为m的路径p为“好”路径： - p可以划分为长度恰好为k的块，即m能被k整除； - c_{p_1} = c_{p_2} = … = c_{p_k}； - c_{p_{k+1}} = c_{p_{k+2}} = … = c_{p_{2k}}； - … - c_{p_{m-k+1}} = c_{p_{m-k+2}} = … = c_{p_{m}}； 任务是找到最大长度的“好”路径的数量。由于这个数字可能太大，所以输出对10^9 + 7取模的结果。 输入数据格式： 每个测试的第一行包含整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含两个整数n和k（1≤k≤n≤5000）——一排瓦片的数量和块长度。 每个测试用例的第二行包含n个整数c_1, c_2, c_3, …, c_n（1≤c_i≤n）——瓦片颜色。 保证所有测试用例的n^2之和不超过25 * 10^6。 输出数据格式： 输出t个数，每个数是对应测试用例的答案——最大长度的“好”路径数量对10^9 + 7取模的结果。 示例输入输出： ``` Input 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 Output 1 4 165 3 1 ``` 注意： 在第一个示例中，无法制作长度大于0的“好”路径。 在第二个示例中，我们关注以下路径： - 1 → 3 → 4 → 5 - 2 → 4 → 5 → 7 - 1 → 3 → 5 → 7 - 1 → 3 → 4 → 7 在第三个示例中，任何长度为8的路径都是“好”路径。