题目描述
小智喜欢数数, 尤其是模 998244353 的积和式。
小智喜欢素数 q , 因此小智也喜欢素域 Fq 。给出 n,q,t , 对于 Fq 上的 n×n 矩阵 C, 如果在所有 n×n 矩阵对 A,B 中 (共 q2n2 对), 恰有 k 对满足 AB=C , 那么定义 C 的价值是 kt 。小智想请你求出所有矩阵 (共 qn2 个) 的价值和对 998244353 取模的结果。
如果你不知道 Fq 是什么, 可以理解为本题的矩阵中每个数都是 ≥0,<q 的整数, 且加法、乘法在对 q 取模下进行。
如果你不知道矩阵是什么, 在本题中, 一个 n×n 矩阵 A 包含 n×n 个数, 排成 n 行 n 列, 第 i 行 j 列的数记作 ai,j 。矩阵 C 是矩阵 A,B 的积, 记作 C=AB , 当且仅 当对于所有 1≤i,j≤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 是素数。
测试点编号 |
n≤ |
q= |
测试点分值 |
1 |
2 |
3 |
1 |
2 |
3 |
4 |
3 |
10 |
11 |
5 |
4 |
50 |
29 |
10 |
5 |
500 |
69965111 |
6 |
5000 |
193785139 |
7 |
106 |
219610337 |
8 |
403753093 |
9 |
107 |
693696533 |
20 |
10 |
896210089 |
【题目来源】
2023 青岛市程序设计竞赛 高中组 T3 matrix