F3. Сверхскоростной подсчёт (сложная версия)
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
NightHawk22 - Isolation
⠀

Это сложная версия задачи. В трёх версиях ограничения на $$$n$$$ и ограничение по времени отличаются. Вы можете совершать взломы только в том случае, если решены все версии задачи.

Это условие задачи D1B:

  • В ряд стоят $$$n$$$ городов, пронумерованных $$$1, 2, \ldots, n$$$ слева направо.
    • В момент времени $$$1$$$ вы захватываете ровно один город, называемый начальным городом.
    • В моменты времени $$$2, 3, \ldots, n$$$ вы можете выбрать город, соседний с уже захваченным, и захватить его.

    Вы выиграете, если для каждого $$$i$$$ вы захватите город $$$i$$$ в момент времени не позже, чем $$$a_i$$$. Выигрышная стратегия может существовать, а может и не существовать, в том числе в зависимости от стартового города. Сколько стартовых городов позволяют вам выиграть?

Для каждого $$$0 \leq k \leq n$$$ подсчитайте количество массивов целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$ таких, что

  • $$$1 \leq a_i \leq n$$$ для каждого $$$1 \leq i \leq n$$$;
  • ответом на задачу D1B будет $$$k$$$.

Ответ может быть очень большим, поэтому вы должны вычислить его по модулю заданного простого числа $$$p$$$.

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

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

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$.

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

Для каждого набора входных данных выведите $$$n+1$$$ целых чисел: $$$i$$$-е целое число должно равняться количеству массивов, удовлетворяющих условиям для $$$k = i-1$$$.

Пример
Входные данные
11
1 998244353
2 998244353
3 998244353
4 998244353
5 998244353
6 998244353
7 998244353
8 998244353
9 998244353
10 102275857
10 999662017
Выходные данные
0 1 
1 2 1 
14 7 4 2 
183 34 19 16 4 
2624 209 112 120 48 12 
42605 1546 793 992 468 216 36 
785910 13327 6556 9190 4672 2880 864 144 
16382863 130922 61939 94992 50100 36960 14256 4608 576 
382823936 1441729 657784 1086596 583344 488700 216000 96480 23040 2880 
20300780 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400 
944100756 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400
Примечание

В первом наборе входных данных,

  • массивы с $$$1$$$ хорошим начальным городом: $$$[1]$$$.

Во втором наборе входных данных,

  • массивы с $$$0$$$ хорошими начальными городами: $$$[1, 1]$$$;
  • массивы с $$$1$$$ хорошим начальным городом: $$$[1, 2]$$$, $$$[2, 1]$$$;
  • массивы с $$$2$$$ хорошими начальными городами: $$$[2, 2]$$$.

В третьем наборе входных данных,

  • массивы с $$$0$$$ хороших начальных городов: $$$[1, 1, 1]$$$, $$$[1, 1, 2]$$$, $$$[1, 1, 3]$$$, $$$[1, 2, 1]$$$, $$$[1, 2, 2]$$$, $$$[1, 3, 1]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 1]$$$, $$$[2, 1, 2]$$$, $$$[2, 2, 1]$$$, $$$[2, 2, 2]$$$, $$$[2, 3, 1]$$$, $$$[2, 3, 2]$$$, $$$[3, 1, 1]$$$;
  • массивы с $$$1$$$ хорошим начальным городом: $$$[1, 2, 3]$$$, $$$[1, 3, 3]$$$, $$$[2, 1, 3]$$$, $$$[3, 1, 2]$$$, $$$[3, 1, 3]$$$, $$$[3, 2, 1]$$$, $$$[3, 3, 1]$$$;
  • массивы с $$$2$$$ хорошими начальными городами: $$$[2, 2, 3]$$$, $$$[2, 3, 3]$$$, $$$[3, 2, 2]$$$, $$$[3, 3, 2]$$$;
  • массивы с $$$3$$$ хорошими начальными городами: $$$[3, 2, 3]$$$, $$$[3, 3, 3]$$$.