Problem Statement

对于集合 $S$，定义 $w(S)=\prod_{x\in S}x$。特别地，定义 $w(\phi)=1$。

记 $[n]$ 表示集合 $\{1,2,\cdots,n\}$，定义 $F(n,k)=\sum_{S\subseteq [n],\lvert S\rvert=k}w(S)$（$0\le k\le n$）。

给定的 $n$ 以及质数 $p$，求出 $\forall i\in [0,p)$，存在多少个 $k\in [0,n]$，满足 $F(n,k)\equiv i\pmod p$。

因为答案可能很大，所以你只要输出答案对 $998,244,353$ 取模的结果即可。

Input Format

一行三个空格隔开的整数 $n,p,T$，其中 $T$ 表示数据类型，其含义请参考输出格式。

Output Format

如果 $T=0$，则输出一行一个整数，表示 $i=0$ 时的答案。

否则，若 $T=1$，则输出 $p$ 行，每行一个整数。其中第 $j$ 行表示 $i=j-1$ 时的答案。

Sample Input

4 5 1

Sample Output

3
1
0
0
1

Sample Explanation

当 $n=4$ 时，$F(n,k)$ 的取值如下：

• $F(4,0)=1$；
• $F(4,1)=1+2+3+4=10$；
• $F(4,2)=2+3+6+4+8+12=35$；
• $F(4,3)=6+8+12+24=50$；
• $F(4,4)=24$；

Constraints

对于所有数据，$T\in \{0,1\}$，$1\le n\le 10^{18}$，$2\le p\le 2\times 10^5$，$p$ 为质数。

• Subtask $1$（$15\%$）：$n\le 5000$；
• Subtask $2,3$（$15\%$，$10\%$）：$p\le 5000$；
• Subtask $4,5$（$20\%$，$15\%$）：$p\le 10^5$；
• Subtask $6,7$（$15\%$，$10\%$）：无特殊限制。

其中，对于编号为偶数的子任务，满足 $T=0$。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$