矩阵的秩（困难版）

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定整数 $n,p,k$，其中 $p$ 为质数。对于每个 $r=0,1,\ldots,k$，求在有限域 $\mathbb F_p$ 上秩恰为 $r$ 的 $n\times n$ 矩阵数量。答案对 $998244353$ 取模。

输入格式

一行三个整数 $n,p,k$。

输出格式

输出 $k+1$ 个整数，依次表示秩为 $0,1,\ldots,k$ 的矩阵数量。

样例输入 1

3 2 3

样例输出 1

1 49 294 168

样例输入 2

1 51549919 2

样例输出 2

1 51549918 0

数据范围

$1\le n\le10^{18}$，$2\le p<998244353$，$0\le k\le5\times10^5$，且 $p$ 为质数。

各子任务数据彼此独立计分。