这是问题的困难版本,它与简单版本的区别仅在于 $$$n$$$ 和 $$$k$$$ 的约束。
Vlad 找到了一行 $$$n$$$ 方块和整数 $$$k$$$。这些图块从左到右进行索引,第 $$$i$$$ 个图块的颜色为 $$$c_i$$$。经过一番思考,他决定如何处理它。
您可以从任何图块开始,向右跳转到任意数量的图块,形成路径 $$$p$$$。如果满足以下条件,我们称长度为 $$$m$$$ 的路径 $$$p$$$ 为“nice”:
- $$$p$$$ 可以被分成长度恰好为 $$$k$$$ 的块,即 $$$m$$$ 可以被 $$$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}}$$$;
你的任务是找到最大长度的好路径的数量。由于这个数字可能太大,因此打印它对 $$$10^9 + 7$$$ 取模。
输入
每个测试的第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — 一行中的图块数量和块的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — 图块颜色。
保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$25 \cdot 10^6$$$。
输出
打印 $$$t$$$ 数字,每个数字都是相应测试用例的答案 - 最大长度模 $$$10^9 + 7$$$ 的好路径的数量。
示例
输入 #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
注意
在第一个示例中,不可能创建长度大于 $$$0$$$ 的良好路径。
在第二个示例中,我们对以下路径感兴趣:
- $$$1 \右箭头 3 \右箭头 4 \右箭头 5$$$
- $$$2 \右箭头 4 \右箭头 5 \右箭头 7$$$
- $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$
- $$$1 \右箭头 3 \右箭头 4 \右箭头 7$$$
在第三个示例中,任何长度为 $$$8$$$ 的路径都可以。