P14928 [北大集训 2025] 深红

给定正整数 $n, m, k$ 以及 $1 \sim k$ 的排列 $p$。 称一个大小为 $n \times m$，元素均为 $[1, k]$ 中的正整数的矩阵为一幅画。对于一幅画 $A$，定义 $A_{i,j}$ 为这个矩阵从上到下第 $i$ 行，从左到右第 $j$ 列的位置的值。 定义两幅画 $A, B$ **相同**，当且仅当对于所有 $1 \le i \le n$，$1 \le j \le m$，均有 $A_{i,j} = B_{i,j}$。以下将两幅画 $A, B$ 相同记作 $A = B$。 定义两幅画 $A, B$ **相似**，当且仅当 $A$ 进行若干次如下两种变换之一可以得到 $B$： 1. 将 $A$ 的第一行移动至最后一行； 2. 将 $A$ 的第一列移动至最后一列。 以下将两幅画 $A, B$ 相似记作 $A \sim B$。 可以证明，二元关系相同和相似均构成等价关系。 对于一幅画 $A$，定义 $f(A)$ 也是一幅画，其中 $f(A)_{i,j} = p_{A_{i,j}}$ ($1 \le i \le n$, $1 \le j \le m$)。 定义一幅画 $A$ 是**优美的**，当且仅当 $f(A) \sim A$。 你需要回答以下两个问题： 1. 最多能选出多少幅优美的画，使得它们**互不相同**？ 2. 最多能选出多少幅优美的画，使得它们**互不相似**？ 由于答案可能较大，你只要求求出答案对 $998,244,353$ 取模后的结果。

从标准输入读入数据。 输入的第一行包含三个正整数 $n, m, k$，表示画的大小与值域。 输入的第二行包含 $k$ 个正整数 $p_1, p_2, \dots, p_k$，表示给定的排列。

输出到标准输出。 输出两行两个非负整数，分别表示最多能选出的**互不相同**与**互不相似**的优美的画的数量对 $998,244,353$ 取模后的结果。 本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见【评分方式】。

### 【子任务】 对于所有测试数据，均有： - $1 \le n, m \le 10^3$，$1 \le k \le 10^6$； - 对于所有 $1 \le i \le k$，$1 \le p_i \le k$，且 $p_1, p_2, \dots, p_k$ 是 $1 \sim k$ 的一个排列。 | 子任务编号 | 分值 | $n, m \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | 1 | $5$ | $16$ | $nm \le 16$ 且 $k \le 2$ | | 2 | $5$ | $10^3$ | 对于所有 $1 \le i \le k$，均有 $p_i = i$ | | 3 | $15$ | $10^3$ | $n = 1$ | | 4 | $20$ | $50$ | $\gcd(n, m) = 1$ | | 5 | $40$ | $50$ | 无 | | 6 | $15$ | $10^3$ | 无 | ### 【评分方式】 对于每个子任务： - 正确回答所有测试数据的最多能选出的**互不相同**的优美的画的数量对 $998,244,353$ 取模后的结果，可获得该子任务 $70\%$ 的分数； - 正确回答所有测试数据的最多能选出的**互不相似**的优美的画的数量对 $998,244,353$ 取模后的结果，可获得该子任务 $30\%$ 的分数。 注意：即使选手仅回答了其中一个问题，也需要按照输出格式输出两个整数，分别对应两个问题的答案。