题目描述

给定正整数 $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$ 取模后的结果。

本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见【评分方式】。

4 4 2
2 1

774
60

8 10 3
1 2 3

412733925
108590870

提示

【子任务】

对于所有测试数据，均有：

• $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		$10^3$	对于所有 $1 \le i \le k$，均有 $p_i = i$
3	$15$		$n = 1$
4	$20$	$50$	$\gcd(n, m) = 1$
5	$40$		无
6	$15$	$10^3$

【评分方式】

对于每个子任务：

• 正确回答所有测试数据的最多能选出的互不相同的优美的画的数量对 $998,244,353$ 取模后的结果，可获得该子任务 $70\%$ 的分数；
• 正确回答所有测试数据的最多能选出的互不相似的优美的画的数量对 $998,244,353$ 取模后的结果，可获得该子任务 $30\%$ 的分数。

注意：即使选手仅回答了其中一个问题，也需要按照输出格式输出两个整数，分别对应两个问题的答案。