CF1811G2 Vlad and the Nice Paths (hard version)

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

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

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

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.