B"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: 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 <= t <= 10^4 ) -- the number of test cases in the test. The first line of each test case contains two integers n and k ( 1 <= k <= n <= 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, ... , c_n ( 1 <= c_i <= 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: In the third example, any path of length 8 is nice. "...