Game of AI (hard version)
Contest: CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3500
Tags: combinatorics, fft, math

This is the hard version of this problem. The difference between easy and hard versions is the constraint on $$$k$$$ and the time limit. Notice that you need to calculate the answer for all positive integers $$$n \in [1,k]$$$ in this version. You can make hacks only if both versions of the problem are solved.

Cirno is playing a war simulator game with $$$n$$$ towers (numbered from $$$1$$$ to $$$n$$$) and $$$n$$$ bots (numbered from $$$1$$$ to $$$n$$$). The $$$i$$$-th tower is initially occupied by the $$$i$$$-th bot for $$$1 \le i \le n$$$.

Before the game, Cirno first chooses a permutation $$$p = [p_1, p_2, \ldots, p_n]$$$ of length $$$n$$$ (A permutation of length $$$n$$$ is an array of length $$$n$$$ where each integer between $$$1$$$ and $$$n$$$ appears exactly once). After that, she can choose a sequence $$$a = [a_1, a_2, \ldots, a_n]$$$ ($$$1 \le a_i \le n$$$ and $$$a_i \ne i$$$ for all $$$1 \le i \le n$$$).

The game has $$$n$$$ rounds of attacks. In the $$$i$$$-th round, if the $$$p_i$$$-th bot is still in the game, it will begin its attack, and as the result the $$$a_{p_i}$$$-th tower becomes occupied by the $$$p_i$$$-th bot; the bot that previously occupied the $$$a_{p_i}$$$-th tower will no longer occupy it. If the $$$p_i$$$-th bot is not in the game, nothing will happen in this round.

After each round, if a bot doesn't occupy any towers, it will be eliminated and leave the game. Please note that no tower can be occupied by more than one bot, but one bot can occupy more than one tower during the game.

At the end of the game, Cirno will record the result as a sequence $$$b = [b_1, b_2, \ldots, b_n]$$$, where $$$b_i$$$ is the number of the bot that occupies the $$$i$$$-th tower at the end of the game.

However, as a mathematics master, she wants you to solve the following counting problem instead of playing games:

Count the number of different pairs of sequences $$$a$$$, $$$b$$$ from all possible choices of sequence $$$a$$$ and permutation $$$p$$$.

Calculate the answers for all $$$n$$$ such that $$$1 \le n \le k$$$. Since these numbers may be large, output them modulo $$$M$$$.

Input format:
The only line contains two positive integers $$$k$$$ and $$$M$$$ ($$$1\le k\le 10^5$$$, $$$2\le M\le 10^9$$$ ). It is guaranteed that $$$2^{18}$$$ is a divisor of $$$M-1$$$ and $$$M$$$ is a prime number.

Output format:
Output $$$k$$$ lines, where the $$$i$$$-th line contains a non-negative integer, which is the answer for $$$n=i$$$ modulo $$$M$$$.

Constraints:
Time limit: 12.0 s
Memory limit: 1024.0 MB

Note:
For $$$n=1$$$, no valid sequence $$$a$$$ exists. We regard the answer as $$$0$$$.

For $$$n=2$$$, there is only one possible array $$$a$$$: $$$[2, 1]$$$.

- For array $$$a$$$ is $$$[2, 1]$$$ and permutation $$$p$$$ is $$$[1, 2]$$$, the sequence $$$b$$$ will be $$$[1, 1]$$$ after all rounds have finished. The details for each rounds:   In the first round, the first bot will begin its attack and successfully capture the tower $$$2$$$. After this round, the second bot will be eliminated and leave the game as all of its towers are occupied by other bots.  In the second round, the second bot is not in the game.
- For array $$$a$$$ is $$$[2, 1]$$$ and permutation $$$p$$$ is $$$[2, 1]$$$, the sequence $$$b$$$ will be $$$[2, 2]$$$ after all rounds have finished. The details for each rounds:   In the first round, the second bot will begin its attack and successfully capture the tower $$$1$$$. After this round, the first bot will be eliminated and leave the game as all of its towers are occupied by other bots.  In the second round, the first bot is not in the game.

So the number of different pairs of sequences $$$(a,b)$$$ is $$$2$$$ ($$$[2, 1]$$$, $$$[1, 1]$$$ and $$$[2, 1]$$$, $$$[2, 2]$$$) for $$$n=2$$$.

Example input:
8 998244353

Example output:
0
2
24
360
6800
153150
4057452
123391016

Editorial:
Given $$$b$$$, The conclusion of possible array $$$a$$$ remains. If we fix array $$$a$$$, we will find that for each $$$i$$$, $$$b_i$$$ will only be $$$j$$$ that $$$a_j=i$$$ or $$$j=i$$$. For any pair $$$(x,y)$$$, if $$$a_x=y$$$, we will find that $$$b_x=x$$$ and $$$b_y=y$$$ at the same time is impossible. All arrays $$$b$$$ which satisfies the above conditions are valid.
So for a fixed array $$$a$$$, and we fix the position that $$$b_i=i$$$(It can be shown that the chosen nodes form a independent set), then the number of possible $$$b$$$ will be product of each in-degree of each $$$x$$$ that $$$b_x\ne x$$$.
Now we can see if we build a graph according to $$$a$$$, the answer will be the sume of product over all independent sets. We need to solve the problem of three parts: the nodes form a tree, some trees' roots form a ring, some trees based on rings form a graph.
For the tree part, let $$$P(x)$$$ be generating function of the sum of pruducts if the root is not included in the independent set, and $$$Q(x)$$$ otherwise. Then we have:
$$$$$$P(x)=x(P(x)+Q(x))e^{P(x)+Q(x)}$$$$$$
$$$$$$Q(x)=xe^{P(x)}$$$$$$
We can solve the equation, and use Newton's method to calculate $$$P(x)$$$ and $$$Q(x)$$$.
Consider how to merge trees together. If one root is not in the independent set, It can either be occupied by one of its children or the previous node on the ring, so its generating function can be represented as $$$A(x)$$$(compared with $$$P(x)$$$, it adds the contribution caused by that it's occupied by the previous node on the ring), which is easy to calculate.
For those which are in the independent set, their previous nodes must not be in. So we binding them together and their generating functions can be represented as $$$B(x)$$$.
The final answer is $$$\sum_{i=1}^{+\infty} \frac{(A(x)+B(x))^i}{i}-A(x)=-\ln(1-A(x)-B(x))-A(x)$$$.
Note that when every node on the ring is occupied by previous node, it is also impossible. So we need to minus this answer. It can be calculated with similar method.
At last, we need to combine these rings into a graph, which can be done with $$$exp$$$ operation.
Time complexity is $$$O(n\log n)$$$.