B - Between B and B Editorial /

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