Это сложная версия задачи, она отличается от простой только ограничениями на \(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\) чисел, каждое из которых является ответом на соответствующий набор входных данных — количество правильных путей максимальной длины по модулю \(10^9 + 7\).
Примечание
В первом примере невозможно составить правильный путь, длины больше \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
4
165
3
1
|