G2. Влад и правильные пути (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи, она отличается от простой только ограничениями на $$$n$$$ и $$$k$$$.

Влад нашёл ряд из $$$n$$$ плиток и число $$$k$$$. Плитки пронумерованы слева направо и $$$i$$$-я плитка имеет цвет $$$c_i$$$. Немного подумав, он решил, что с этим делать.

Вы можете начать с любой плитки и прыгать на любое количество плиток вправо, формируя при этом путь $$$p$$$. Назовём путь $$$p$$$ длины $$$m$$$ правильным, если верно:

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

Пример
Входные данные
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
4
165
3
1
Примечание

В первом примере невозможно составить правильный путь, длины больше $$$0$$$.

Во втором примере нас интересуют следующие пути:

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

В третьем примере подходит любой путь длины $$$8$$$.