题目描述

这是一道 模板题。

给定正整数 $n,q,mod$。保证 $mod$ 是质数。

对于一棵以点 $1$ 为根的有根树 $T$，设 $s(T)$ 为这棵树中最多能选出多少个互不同构的子树（也就是这颗树本质不同的子树个数），那么这个树的权值 $w(T) = q^{s(T)}$。

对于所有 $1 \le m \le n$，输出所有大小为 $m$，根为 $1$ 的有标号树的权值之和对 $mod$ 取模后的值。

两棵有根树 $T_1$、$T_2$ 同构当且仅当他们的大小相等，且存在一个顶点排列 $\sigma$ 使得在 $T_1$ 中 $i$ 是 $j$ 的祖先当且仅当在 $T_2$ 中 $\sigma(i)$ 是 $\sigma(j)$ 的祖先。

输入格式

一行两个整数，表示 $n,q,mod$。

输出格式

输出 $n$ 行，第 $m$ 行表示 $m$ 个点的答案。

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

提示

样例解释 1

$n=3,q=2,mod=998244353$ 时，有三颗不同三个点的根为 $1$ 的有标号树，其中两颗满足 $w(T)=2^3$，另一颗满足 $w(T)=2^2$。因此答案为 $(2 \times 2^3+2^2) \bmod 998244353 = 20$。

限制与约定

对于所有测试数据，保证 $n = 100, 10^8 \le mod \le 1.01 \times 10^9, 1 \le q < mod$，且 $mod$ 是质数。

本题共 $1$ 个子任务，每个子任务 $100$ 分。你在每个子任务中的得分为该子任务所有测试点的得分的最小值。

你必须按照输出格式输出 $n$ 个数，但是你可以输出错误的答案。如果你输出了 $c$ 个正确的答案，那么你获得的分数按照如下方式计算：

• 对于 $0 \le c \le 20$，你的得分为 $2c$ 分；
• 对于 $21 \le c \le 60$，你的得分为 $c + 20$ 分。
• 对于 $61 \le c \le 100$，你的得分为 $\lfloor \frac{c}{2}\rfloor + 50$ 分。

时间限制：$\texttt{4s}$。 空间限制：$\texttt{2048MB}$。

你可以使用下面的代码来加速你的取模。

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';
}