H2. Игра ИИ (сложная версия)
ограничение по времени на тест
12 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия этой задачи. Разница между легкой и сложной версиями заключается в ограничении на $$$k$$$ и ограничении по времени. Кроме того, в этой версии вам нужно вычислить ответ для всех положительных целых чисел $$$n \in [1,k]$$$ в этой версии. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Cirno играет в военный симулятор с $$$n$$$ башнями (пронумерованными от $$$1$$$ до $$$n$$$) и $$$n$$$ ботами (пронумерованными от $$$1$$$ до $$$n$$$). Первоначально $$$i$$$-я башня занята $$$i$$$-м ботом для всех $$$1 \le i \le n$$$.

Перед игрой Cirno сначала выбирает перестановку $$$p = [p_1, p_2, \ldots, p_n]$$$ длины $$$n$$$ (перестановкой длины $$$n$$$ называется массив длины $$$n$$$, где каждое целое число между $$$1$$$ и $$$n$$$ встречаются ровно один раз). После этого она может выбрать последовательность $$$a = [a_1, a_2, \ldots, a_n]$$$ ($$$1 \le a_i \le n$$$ и $$$a_i \ne i$$$ для всех $$$1 \le i \le n$$$ ).

В игре есть $$$n$$$ раундов-атак. В $$$i$$$-м раунде, если $$$p_i$$$-й бот все еще находится в игре, он начнет свою атаку, в результате чего $$$a_{p_i}$$$-я башня будет занята $$$p_i$$$-м ботом; бот, который ранее занимал $$$a_{p_i}$$$-ю башню, больше не будет ее занимать. Если $$$p_i$$$-го бота нет в игре, в этом раунде ничего не произойдет.

После каждого раунда, если бот не занимает ни одной башни, он будет уничтожен и покинет игру. Обратите внимание, что ни одна башня не может быть занята более чем одним ботом, но один бот может занимать более одной башни во время игры.

В конце игры Cirno запишет результат в виде последовательности $$$b = [b_1, b_2, \ldots, b_n]$$$, где $$$b_i$$$ — номер бота, занимающего $$$i$$$-ю башня в конце игры.

Однако, как мастер математики, она хочет, чтобы вы решили следующую задачу на счет вместо того, чтобы играть в игры:

Подсчитайте количество различных пар последовательностей $$$a$$$ и $$$b$$$, которые могут получиться при всех возможных выборах последовательности $$$a$$$ и перестановки $$$p$$$.

Вычислите ответ для всех значений $$$n$$$ таких, что $$$1 \le n \le k$$$. Так как эти числа могут быть большими, выведите их по модулю $$$M$$$.

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

Единственная строка содержит два натуральных числа $$$k$$$ и $$$M$$$ ($$$1\le k\le 10^5$$$, $$$2\le M\le 10^9$$$ ). Гарантируется, что $$$2^{18}$$$ — делитель $$$M-1$$$, а $$$M$$$ — простое число.

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

Выведите $$$k$$$ строк, где $$$i$$$-я строка содержит неотрицательное целое число, являющееся ответом для $$$n=i$$$ по модулю $$$M$$$.

Пример
Входные данные
8 998244353
Выходные данные
0
2
24
360
6800
153150
4057452
123391016
Примечание

Для $$$n=1$$$ допустимой последовательности $$$a$$$ не существует. Мы рассматриваем ответ как $$$0$$$.

При $$$n=2$$$ возможен только один массив $$$a$$$: $$$[2, 1]$$$.

  • Для массива $$$a$$$ равного $$$[2, 1]$$$ и перестановки $$$p$$$ равной $$$[1, 2]$$$, последовательность $$$b$$$ будет $$$[1, 1]$$$ после всех раундов. Детали для каждого раунда:
    • В первом раунде первый бот начнет атаку и успешно захватит башню $$$2$$$. После этого раунда второй бот будет уничтожен и покинет игру, так как все его башни заняты другими ботами.
    • Во втором раунде второго бота нет в игре.
  • Для массива $$$a$$$ равного $$$[2, 1]$$$ и перестановки $$$p$$$ равной $$$[2, 1]$$$, последовательность $$$b$$$ будет $$$[2, 2]$$$ после всех раундов. Детали для каждого раунда:
    • В первом раунде второй бот начнет атаку и успешно захватит башню $$$1$$$. После этого раунда первый бот будет уничтожен и покинет игру, так как все его башни заняты другими ботами.
    • Во втором раунде первого бота нет в игре.

Таким образом, количество различных пар последовательностей $$$(a,b)$$$ равно $$$2$$$ ($$$[2, 1]$$$, $$$[1, 1]$$$ и $$$[2, 1]$$$, $$$[2, 2]$$$) при $$$n=2$$$.