Counting Permutations Yielding a Specific Longest Common Subsequence

Consider a permutation \( p \) of \( \{1,2,\dots, n\} \). Define two subsequences of \( p \) of length \( k \) as follows:

• \( S_0 \) is the lexicographically largest subsequence of length \( k \) of \( p \).
• \( S_1 \) is the lexicographically smallest subsequence of length \( k \) of \( p \).

The two experts, one from Japan and one from China, each independently choose a subsequence of length \( k \). One chooses \( S_0 \) and the other chooses \( S_1 \). On a note they record one of the longest common subsequences (LCS) of \( S_0 \) and \( S_1 \) (this LCS is not necessarily unique). Many years later, you find that note. You wonder: how many possible permutations \( p \) (i.e. solutions) could have eventually led to the appearance of that note?

More formally, you are given three integers \( n \), \( k \) and \( m \) along with a sequence \( Q = [q_1, q_2, \dots, q_m] \) (recorded on the note). For each permutation \( p \) of \( \{1,2,\dots,n\} \), let \( S_0(p) \) be its lexicographically largest subsequence of length \( k \) and \( S_1(p) \) be its lexicographically smallest subsequence of length \( k \). Let \( L \) denote the length of the longest common subsequence of \( S_0(p) \) and \( S_1(p) \) (computed in the usual way using dynamic programming). We say that \( p \) is valid if:

1. \( Q \) is a subsequence of \( S_0(p) \) and of \( S_1(p) \), and
2. \( m = L \) (i.e. \( Q \) is indeed one of the LCS of \( S_0(p) \) and \( S_1(p) \)).

Output the number of valid permutations \( p \) modulo \( 998244353 \).

Notes on subsequences:

• The lexicographically largest subsequence of length \( k \) can be computed by a greedy stack algorithm. In particular, for a sequence \( a_1,a_2,\dots,a_n \), one may iterate from \( 1 \) to \( n \) and maintain a stack \( S \) so that while \( S \) is nonempty, the current element is greater than the top of \( S \) and there are enough remaining elements to fill the subsequence to length \( k \), you pop from \( S \); then, if \( |S|< k \), you push the current element.
• The lexicographically smallest subsequence is obtained by a similar algorithm but replacing the comparison by > with <.

Input constraints: Because the intended solution uses brute force over all \( n! \) permutations, you may assume \( n \) is small (for example, \( n \le 8 \)).

inputFormat

The first line contains three integers \( n \), \( k \) and \( m \) (with \( 1 \le k \le n \le 8 \) and \( 1 \le m \le k \)). The second line contains \( m \) integers \( q_1, q_2, \dots, q_m \), representing the sequence recorded on the note.

\( Q \) is guaranteed to consist of distinct integers from \( 1 \) to \( n \).

outputFormat

Output a single integer, the number of permutations \( p \) that are valid (i.e. for which the lexicographically largest subsequence \( S_0(p) \) and the lexicographically smallest subsequence \( S_1(p) \) have a longest common subsequence equal to \( Q \)), modulo \( 998244353 \).

sample

3 2 1
2

4