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 node $1$, let $s(T)$ be the maximum number of pairwise non-isomorphic subtrees that can be chosen from this tree (that is, the number of essentially different subtrees of this tree). Then the weight of this tree is $w(T) = q^{s(T)}$.

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

Two rooted trees $T_1$ and $T_2$ are isomorphic if and only if they have the same size, and there exists a vertex 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

One line with two integers, representing $n, q, mod$.

Output Format

Output $n$ lines. Line $m$ gives the answer for $m$ nodes.

3 2 998244353

2
4
20

11 4514 998244353

4514
20376196
299712732
706663250
721357660
977589073
794002114
369586566
663682963
347458730
524354925

40 787788 998244853

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

Hint

Sample Explanation 1

When $n = 3, q = 2, mod = 998244353$, there are three different labeled trees with three nodes and root $1$. Two of them satisfy $w(T) = 2^3$, and the other one satisfies $w(T) = 2^2$. Therefore, the answer is $(2 \times 2^3 + 2^2) \bmod 998244353 = 20$.

Constraints and Notes

For all testdata, 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 has $1$ subtask, and each subtask is worth $100$ points. Your score for each subtask is the minimum score among all test points in that subtask.

You must output $n$ numbers according to the output format, but you are allowed to 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}$. Memory 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';
}

Translated by ChatGPT 5