Это сложная версия задачи. Единственное различие между двумя версиями — ограничение на \(n\). Вы можете делать взломы, только если обе версии задачи решены.
Массив \(b\) из \(m\) целых неотрицательных чисел считается хорошим, если все элементы \(b\) можно сделать равными \(0\) с помощью применения следующей операции несколько (возможно, ноль) раз:
- Выбрать два различных индекса \(l\) и \(r\) (\(1 \leq l \color{red}{<} r \leq m\)) и вычесть \(1\) из всех \(b_i\) таких, что \(l \leq i \leq r\).
Вам даны три целых положительных числа \(n\), \(k\) и простое число \(p\).
Среди всех \((k+1)^n\) массивов длины \(n\), таких, что \(0 \leq a_i \leq k\) для всех \(1 \leq i \leq n\), посчитайте количество хороших массивов.
Поскольку число может быть очень большим, от вас требуется найти его только по модулю \(p\).
Выходные данные
Для каждого набора входных данных в новой строке выведите количество хороших массивов по модулю \(p\).
Примечание
В первом наборе входных данных \(4\) хорошими массивами \(a\) являются:
- \([0,0,0]\);
- \([0,1,1]\);
- \([1,1,0]\);
- \([1,1,1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353
|
4
7
10
456615865
|