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

Это сложная версия задачи. Единственное различие между двумя версиями — ограничение на $$$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$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых положительных числа $$$n$$$, $$$k$$$ и $$$p$$$ ($$$3 \leq n \leq 3000$$$, $$$1 \leq k \leq n$$$, $$$10^8 < p < 10^9$$$) — длина массива $$$a$$$, верхняя граница на элементы $$$a$$$ и модуль $$$p$$$.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^7$$$, а $$$p$$$ является простым.

Выходные данные

Для каждого набора входных данных в новой строке выведите количество хороших массивов по модулю $$$p$$$.

Пример
Входные данные
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353
Выходные данные
4
7
10
456615865
Примечание

В первом наборе входных данных $$$4$$$ хорошими массивами $$$a$$$ являются:

  • $$$[0,0,0]$$$;
  • $$$[0,1,1]$$$;
  • $$$[1,1,0]$$$;
  • $$$[1,1,1]$$$.