题目描述

小智喜欢数数, 尤其是模 $998244353$ 的积和式。

小智喜欢素数 $q$ , 因此小智也喜欢素域 $\mathbf{F}_{q}$ 。给出 $n, q, t$ , 对于 $\mathbf{F}_{q}$ 上的 $n \times n$ 矩阵 $C$, 如果在所有 $n \times n$ 矩阵对 $A, B$ 中 (共 $q^{2 n^{2}}$ 对), 恰有 $k$ 对满足 $AB=C$ , 那么定义 $C$ 的价值是 $k^{t}$ 。小智想请你求出所有矩阵 (共 $q^{n^{2}}$ 个) 的价值和对 $998244353$ 取模的结果。

如果你不知道 $\mathbf{F}_{q}$ 是什么, 可以理解为本题的矩阵中每个数都是 $\geq 0,<q$ 的整数, 且加法、乘法在对 $q$ 取模下进行。

如果你不知道矩阵是什么, 在本题中, 一个 $n \times n$ 矩阵 $A$ 包含 $n \times n$ 个数, 排成 $n$ 行 $n$ 列, 第 $i$ 行 $j$ 列的数记作 $a_{i, j}$ 。矩阵 $C$ 是矩阵 $A, B$ 的积, 记作 $C=A B$ , 当且仅 当对于所有 $1 \leq i, j \leq n$ , 有 $c_{i, j} \equiv \sum_{k=1}^{n} a_{i, k} b_{k, j}(\bmod q) $。

输入格式

一行，包含三个正整数 $n, q, t$，含义如题中所述。

输出格式

一行，包含一个数，表示答案。

样例输入输出

2 2 2

6496

10 3 2

475440451

1000 686902939 3

104612575

说明/提示

【数据范围及约束】

对于所有数据, 保证 $2 \leq n \leq 10^{7}, 2 \leq q<998244353,2 \leq t \leq 20$, $q$ 是素数。

【题目来源】

2023 青岛市程序设计竞赛 高中组 T3 matrix