Problem Description

This is a template problem.

Given positive integers $n, q, mod$. It is guaranteed that $mod$ is a prime number.

For a rooted tree $T$ with root at vertex $1$, let $s(T)$ be the maximum number of non-isomorphic subtrees that can be selected from this tree (i.e., the number of distinct subtrees of the tree), then the weight of this tree $w(T) = q^{s(T)}$.

For all $1 \le m \le n$, output the sum of the weights of all labeled trees of size $m$ with root at vertex $1$, modulo $mod$.

Two rooted trees $T_1$ and $T_2$ are isomorphic if and only if they have the same size, and there exists a permutation $\sigma$ such that in $T_1$, $i$ is an ancestor of $j$ if and only if in $T_2$, $\sigma(i)$ is an ancestor of $\sigma(j)$.

Input Format

A single line containing three integers, representing $n, q, mod$.

Output Format

Output $n$ lines, where the $m$-th line represents the answer for $m$ points.

Sample Input and Output

Input Sample #1

3 2 998244353

Output Sample #1

2
4
20

Input Sample #2

11 4514 998244353

Output Sample #2

4514
20376196
299712732
706663250
721357660
977589073
794002114
369586566
663682963
347458730
524354925

Input Sample #3

40 787788 998244853

Output Sample #3

787788
699879231
445785131
857102003
759492151
898159394
575712517
634469464
412999753
814233648
333451903
852329440
584109489
270769240
532457985
79235443
2228568
266810999
310877128
614605839
485785485
338520973
113751992
692026056
664258393
650448721
505881810
237159658
107178163
629910112
513627947
915509519
737809847
921731327
233492829
202989716
728903945
776060784
105388817
121481849

Notes/Hints

Sample Explanation 1

For $n=3, q=2, mod=998244353$, there are three different labeled trees with three points and root at vertex $1$. Two of them have $w(T)=2^3$, and the other has $w(T)=2^2$. Therefore, the answer is $(2 \times 2^3 + 2^2) \bmod 998244353 = 20$.

Constraints and Specifications

For all test data, it is guaranteed that $n = 100, 10^8 \le mod \le 1.01 \times 10^9, 1 \le q < mod$, and $mod$ is a prime number.

This problem consists of $1$ sub-task, each sub-task worth $100$ points. Your score for each sub-task is the minimum score among all test cases in that sub-task.

You must output $n$ numbers in the specified format, but you can output incorrect answers. If you output $c$ correct answers, your score is calculated as follows:

• For $0 \le c \le 20$, your score is $2c$ points;
• For $21 \le c \le 60$, your score is $c + 20$ points;
• For $61 \le c \le 100$, your score is $\lfloor \frac{c}{2}\rfloor + 50$ points.

Time limit: $\texttt{4s}$.
Space limit: $\texttt{2048MB}$.

You can use the following code to speed up your modulo operations.

struct fastmod {
  typedef unsigned long long u64;
  typedef __uint128_t u128;

  int m;
  u64 b;

  fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
  int reduce(u64 a) {
    u64 q = ((u128)a * b) >> 64;
    int r = a - q * m;
    return r < m ? r : r - m;
  }
} z(2);
void solve() {
    long long mod = 998244353, qwq = 1e9;
    z = fastmod(mod);
    cout << z.reduce(qwq) << ' ' << qwq % mod << '\n';
}

见题面 Input 部分

见题面 Output 部分