Perfect Arrays and Colorings

You are given an array \(A\) of length \(n\) consisting of positive integers, where each element is in the range \(\{1,2,\ldots, m\}\). The numbers are arranged from left to right. You have to color each number either red or green. A coloring scheme is called good if and only if:

• Every element \(A_i\) is colored either red or green.
• The red subsequence (i.e. the sequence of numbers colored red in the original order) is strictly increasing.
• The green subsequence (i.e. the sequence of numbers colored green in the original order) is strictly decreasing.

For example, consider the array \(1\;9\;3\;4\;7\;6\). Coloring \(1,3,4,7\) red and \(9,6\) green is a good scheme as the red numbers \(1<3<46\). Also, coloring \(1,4,6\) red and \(9,7\) green is good. However, coloring \(1,4,7,6\) red and \(9,3\) green is not good because \(1,4,7,6\) is not strictly increasing. Note that if a subsequence contains 0 or 1 element, it is trivially considered strictly monotonic. For instance, 123 colored entirely in red and 1 red, 2 green, 3 red are both valid good schemes.

An array \(A\) is called perfect if it admits at least two different good coloring schemes (two schemes are considered different if there is at least one position where the colors differ). For example, the arrays \(1\;9\;3\;4\;7\;6\) and \(1\;9\;5\;5\) are perfect, while \(2\;3\;3\;3\) is not, since it has no good coloring scheme. Also, \(1\;5\;3\;6\;4\) is not perfect because it admits only one good scheme.

We further define a scoring mechanism for a coloring scheme. For every ordered pair \((i,j)\) with \(i < j\), the score contributed by the pair is determined by:

• If \(A_j\) is colored red and \(A_j < A_i\), then the pair scores \(m - A_j + 1\) points.
• If \(A_j\) is colored green and \(A_j > A_i\), then the pair scores \(A_j\) points.
• Otherwise, the pair scores 0 points.

The score of a coloring scheme is the sum over all ordered pairs, and the score of a perfect array is defined as the maximum score among all its good coloring schemes.

You are given the first \(t\) elements \(A_1, A_2, \ldots, A_t\) of the array \(A\). Your task is to answer two questions:

1. How many ways are there to choose the remaining \(n-t\) elements (each in \(\{1,2,\ldots, m\}\)) such that the complete array \(A\) is perfect?
2. What is the sum of the scores of all possible perfect arrays?

Since the answers can be very large, output them modulo \(998244353\).

inputFormat

The first line contains three integers \(n\), \(m\) and \(t\) (1 \le t \le n). The second line contains \(t\) integers \(A_1, A_2, \ldots, A_t\), each between \(1\) and \(m\) (inclusive).

outputFormat

Output two integers, separated by a space:

• The number of ways to choose the remaining \(n-t\) elements such that \(A\) is perfect, modulo \(998244353\).
• The sum of the scores of all perfect arrays modulo \(998244353\).

sample

3 3 1
1

8 21