write a go solution for Description:
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 Format:
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*10^6.

Output Format:
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.

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:

- 1arrow3arrow4arrow5
- 2arrow4arrow5arrow7
- 1arrow3arrow5arrow7
- 1arrow3arrow4arrow7

In the third example, any path of length 8 is nice.. Output only the code with no comments, explanation, or additional text.