Problem Description

Given a positive integer array $A$ of length $n$, where each number is between $1$ and $m$, arranged from left to right. Now we want to color each number either red or green. We call a coloring scheme an excellent coloring scheme if and only if it satisfies:

1. Each number $A_{i}$ is colored either red or green.
2. The red numbers are strictly increasing from left to right, and the green numbers are strictly decreasing from left to right.

For example, in $1\;9\;3\;4\;7\;6$, coloring $1\;3\;4\;7$ red and $9\;6$ green is an excellent coloring scheme ($\color{red}1\color{green}9\color{red}347\color{green}6$). Coloring $1\;3\;4\;6$ red and $9\;7$ green is also an excellent coloring scheme ($\color{red}1\color{green}9\color{red}34\color{green}7\color{red}6$). However, coloring $1\;4\;7\;6$ red and $9\;3$ green is not an excellent coloring scheme, because $1\;4\;7\;6$ is not increasing. In $1\;9\;5\;5$, coloring $1$ and either one of the $5$'s red, and coloring $9$ and the other $5$ green, is also an excellent coloring scheme (one possible scheme is $\color{red}1\color{green}95\color{red}5$).

If an array has at least two different excellent coloring schemes, then this array is called perfect. (Two coloring schemes are different if and only if there exists at least one position where the number is colored differently.)

For example, $1\;9\;3\;4\;7\;6$ and $1\;9\;5\;5$ are both perfect, because $2$ excellent coloring schemes have already been given for each above. But $2\;3\;3\;3$ is not perfect, because no excellent coloring scheme exists. Also, $1\;5\;3\;6\;4$ is not perfect, because there is only one excellent coloring scheme ($\color{red}1\color{green}5\color{red}36\color{green}4$).

Additional note: If there are only $0$ or $1$ red numbers, we also consider them strictly increasing; similarly, if there are only $0$ or $1$ green numbers, we also consider them strictly decreasing. For example, $\color{red}123$ and $\color{red}1\color{green}2\color{red}3$ are both excellent coloring schemes, so $1\;2\;3$ is a perfect array.

We define a way to score a coloring scheme.

For each ordered pair of elements $A_{i}, A_{j}(i<j)$:

1. If $A_{j}$ is colored red and $A_{j}<A_{i}$, then this pair scores $m-A_{j}+1$ points.
2. If $A_{j}$ is colored green and $A_{j}>A_{i}$, then this pair scores $A_{j}$ points.
3. If neither 1 nor 2 is satisfied, then this pair scores $0$ points.

Then the score of a coloring scheme is the sum of scores over all ordered pairs.

The score of a perfect array is the maximum score among all its excellent coloring schemes.

Now the first $t$ numbers $A_{1}, A_{2}, \ldots, A_{t}$ of array $A$ are fixed. You need to answer the following two questions:

• Question 1: How many ways are there to determine the remaining $n-t$ numbers of $A$ such that $A$ is a perfect array?
• Question 2: What is the sum of the scores of all possible perfect arrays?

Since the answer can be very large, you only need to output the result modulo $998244353$.

Input Format

This problem contains multiple test cases.

The first line of input contains a positive integer $C$, denoting the number of test cases.

Then there are $C$ test cases. Each test case is formatted as follows:

The first line contains three integers $n, m, t$, denoting the array length, the maximum value in the array, and the length of the fixed prefix.

The second line contains $t$ positive integers $A_{1} \ldots A_{t}$, denoting the fixed prefix.

Output Format

For each test case, output one line containing two integers separated by a single space.

• The first integer is the number of perfect arrays modulo $998244353$.

• The second integer is the sum of scores of all perfect arrays modulo $998244353$.

5
6 10 6
1 9 3 4 7 6
5 8 4
1 7 2 6
9 10 2
3 6
6 11 6
1 7 5 8 3 9
9 10 5
5 10 6 4 7

1 63
8 245
29378 1267731
1 17
78 1820

见附件中的 color/color2.in

见附件中的 color/color2.ans

Hint

【Scoring】

Each test point is worth $5$ points.

Each line should output the answers to the two questions in order. Any output that does not match the required format will get $0$ points.

If your program answers only Question 1 correctly, you get $1$ point. If it answers only Question 2 correctly, you get $4$ points. If it answers both correctly, you get $5$ points.

If you do not answer Question 1 or Question 2, you still need to output any integer in the corresponding position to satisfy the output format.

【Subtasks】

For all testdata, it is guaranteed that: $1 \leq C \leq 5$; $2 \leq n \leq 50$; $1 \leq t \leq n$; $1 \leq m \leq 200$; $1 \leq A_{i} \leq m$.

Translated by ChatGPT 5