[Solution] Game of AI (hard version) Codeforces Solution

H2. Game of AI (hard version)

time limit per test

12 seconds

memory limit per test

1024 megabytes

input

standard input

output

standard output

This is the hard version of this problem. The difference between easy and hard versions is the constraint on k$k$ and the time limit. Notice that you need to calculate the answer for all positive integers n∈[1,k]$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$n$ towers (numbered from 1$1$ to n$n$) and n$n$ bots (numbered from 1$1$ to n$n$). The i$i$-th tower is initially occupied by the i$i$-th bot for 1≤i≤n$1\le i\le n$.

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

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied the api$a_{p_i}$-th tower will no longer occupy it. If the pi$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=[b1,b2,…,bn]$b=[b_1,b_2,\dots ,b_n]$, where bi$b_i$ is the number of the bot that occupies the i$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$a$, b$b$ from all possible choices of sequence a$a$ and permutation p$p$.

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

Input

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

Output

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