Given positive integers $n, m, k$ and a permutation $p$ of $1 \sim k$.
A matrix of size $n \times m$ with all elements being positive integers in $[1, k]$ is called a painting. For a painting $A$, let $A_{i,j}$ be the value at the $i$-th row from the top and $j$-th column from the left.
Two paintings $A$ and $B$ are defined as identical if and only if $A_{i,j} = B_{i,j}$ for all $1 \le i \le n, 1 \le j \le m$. We denote this as $A = B$.
Two paintings $A$ and $B$ are defined as similar if and only if $B$ can be obtained from $A$ by applying a finite number of the following two transformations: 1. Move the first row of $A$ to the last row. 2. Move the first column of $A$ to the last column.
We denote this as $A \sim B$. It can be proven that both "identical" and "similar" are equivalence relations.
For a painting $A$, define $f(A)$ as a painting where $f(A)_{i,j} = p_{A_{i,j}}$ for all $1 \le i \le n, 1 \le j \le m$. A painting $A$ is defined as beautiful if and only if $f(A) \sim A$.
You need to answer the following two questions: 1. What is the maximum number of beautiful paintings that can be chosen such that they are pairwise not identical? 2. What is the maximum number of beautiful paintings that can be chosen such that they are pairwise not similar?
Since the answers may be large, you only need to output the results modulo $998,244,353$.
Input
The first line contains three positive integers $n, m, k$, representing the size of the painting and the range of values. The second line contains $k$ positive integers $p_1, p_2, \dots, p_k$, representing the given permutation.
Output
Output two lines, each containing a non-negative integer, representing the maximum number of pairwise not identical and pairwise not similar beautiful paintings, respectively, modulo $998,244,353$.
This problem consists of two sub-questions; answering either one correctly will earn partial points. Please refer to the "Scoring" section for details.
Constraints
For all test data: $1 \le n, m \le 10^3$, $1 \le k \le 10^6$; For all $1 \le i \le k$, $1 \le p_i \le k$, and $p_1, p_2, \dots, p_k$ is a permutation of $1 \sim k$.
| Subtask | Score | $n, m \le$ | Special Property |
|---|---|---|---|
| 1 | 5 | 16 | $nm \le 16$ and $k \le 2$ |
| 2 | 10 | $10^3$ | For all $1 \le i \le k$, $p_i = i$ |
| 3 | 15 | $10^3$ | $n = 1$ |
| 4 | 20 | 50 | $\gcd(n, m) = 1$ |
| 5 | 40 | 50 | None |
| 6 | 15 | $10^3$ | None |
Examples
Input 1
1 4 4 2 2 2 1
Output 1
774 60
Input 2
8 10 3 1 2 3
Output 2
412733925 108590870
Scoring
For each subtask: Correctly answering the maximum number of pairwise not identical beautiful paintings modulo $998,244,353$ for all test cases in the subtask earns 70% of the points for that subtask. Correctly answering the maximum number of pairwise not similar beautiful paintings modulo $998,244,353$ for all test cases in the subtask earns 30% of the points for that subtask.
Note: Even if you only answer one of the questions, you must still output two integers according to the output format, corresponding to the answers for both questions.