

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 以上 M 以下の整数からなる長さ M の数列 (X_1,X_2,\dots ,X_M) が与えられます.
1 以上 M 以下の整数からなる長さ N の数列 A=(A_1,A_2,\dots ,A_N) であって, 以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください.
- B=1,2,\dots ,M について, A の中で異なる位置にある 2 つの B の間(両端を含む)には X_B が存在する.
より正確には, B=1,2,\dots ,M について次の条件が成り立つことを言います.
- 1\le l\lt r\le N かつ A_l=A_r=B を満たすすべての整数組 (l,r) に対して, ある整数 m\ (l\le m\le r) が存在して, A_m=X_B が成り立つ.
制約
- 1\leq M\leq 10
- 1 \leq N \leq 10^4
- 1 \leq X_i \leq M
- 入力される値はすべて整数.
入力
入力は以下の形式で標準入力から与えられる.
M N X_1 X_2 \cdots X_M
出力
答えを出力せよ.
入力例 1
3 4 2 1 2
出力例 1
14
条件を満たす A としては例えば次のものが挙げられます.
- (1,3,2,3)
- (2,1,2,1)
- (3,2,1,3)
逆に, 次のものは条件を満たしません.
- (1,3,1,3)
- 3 の間に X_3=2 がありません
- (2,2,1,3)
- 2 の間に X_2=1 がありません
入力例 2
4 8 1 2 3 4
出力例 2
65536
1 以上 4 以下の整数からなる長さ 8 の数列はすべて条件を満たします.
X_B=B のとき, 異なる位置にある B の間には必ず B が存在することに注意してください.
入力例 3
4 9 2 3 4 1
出力例 3
628
Score : 500 points
Problem Statement
You are given a sequence (X_1, X_2, \dots, X_M) of length M consisting of integers between 1 and M, inclusive.
Find the number, modulo 998244353, of sequences A = (A_1, A_2, \dots, A_N) of length N consisting of integers between 1 and M, inclusive, that satisfy the following condition:
- For each B = 1, 2, \dots, M, the value X_B exists between any two different occurrences of B in A (including both ends).
More formally, for each B = 1, 2, \dots, M, the following condition must hold:
- For every pair of integers (l, r) such that 1 \leq l < r \leq N and A_l = A_r = B, there exists an integer m (l \leq m \leq r) such that A_m = X_B.
Constraints
- 1 \leq M \leq 10
- 1 \leq N \leq 10^4
- 1 \leq X_i \leq M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
M N X_1 X_2 \cdots X_M
Output
Print the answer.
Sample Input 1
3 4 2 1 2
Sample Output 1
14
Here are examples of sequences A that satisfy the condition:
- (1, 3, 2, 3)
- (2, 1, 2, 1)
- (3, 2, 1, 3)
Here are non-examples:
- (1, 3, 1, 3)
- There is no X_3 = 2 between the 3s.
- (2, 2, 1, 3)
- There is no X_2 = 1 between the 2s.
Sample Input 2
4 8 1 2 3 4
Sample Output 2
65536
All sequences of length 8 consisting of integers between 1 and 4 satisfy the condition.
Note that when X_B = B, there is always a B between two different occurrences of B.
Sample Input 3
4 9 2 3 4 1
Sample Output 3
628