H2. 矩阵秩（困难版）

每个测试点时间限制：$2$ 秒
内存限制：$256$ 兆字节

这是该问题的困难版本。两个版本之间的唯一区别在于对 $k$ 的约束不同。只有当两个版本的问题都解决后，你才能进行 hack。

给定整数 $n$、$p$ 和 $k$。保证 $p$ 是素数。

对于每个 $r$ 从 $0$ 到 $k$，求在模 $p$ 的整数域† 上，所有 $n \times n$ 矩阵 $A$ 中，秩‡ 恰好等于 $r$ 的矩阵个数。由于这些数值很大，你只需输出它们对 $998244353$ 取模的结果。

† 域（数学）
‡ 秩（线性代数）

输入
第一行包含三个整数 $n$、$p$ 和 $k$（$1 \le n \le 10^{18}$，$2 \le p < 998244353$，$0 \le k \le 5 \cdot 10^5$）。
保证 $p$ 是素数。

输出
输出 $k+1$ 个整数，分别对应 $r = 0, 1, \dots, k$ 时的答案。

示例

输入

3 2 3  

输出

1 49 294 168  

输入

1 51549919 2  

输出

1 51549918 0