题目描述

给定一个由 $1$ 到 $M$ 之间的整数构成的长度为 $M$ 的数列 $(X_1, X_2, \dots, X_M)$。

请计算满足以下条件的长度为 $N$ 的数列 $A = (A_1, A_2, \dots, A_N)$ 的个数，并对 $998244353$ 取模。

• 对于每个 $B=1,2,\dots,M$，在 $A$ 中任意两个不同位置的 $B$ 之间（包括两端），都存在 $X_B$。

更准确地说，对于每个 $B=1,2,\dots,M$，都满足以下条件：

• 对于所有满足 $1 \leq l < r \leq N$ 且 $A_l = A_r = B$ 的整数对 $(l, r)$，都存在一个整数 $m$，使得 $l \leq m \leq r$ 且 $A_m = X_B$。

输入格式

输入以如下格式从标准输入读入：

$M$ $N$ $X_1$ $X_2$ $\cdots$ $X_M$

输出格式

输出满足条件的数列 $A$ 的个数，对 $998244353$ 取模。

样例 1

输入

3 4
2 1 2

输出

14

样例 2

输入

4 8
1 2 3 4

输出

65536

样例 3

输入

4 9
2 3 4 1

输出

628

说明/提示

限制

• $1 \leq M \leq 10$
• $1 \leq N \leq 10^4$
• $1 \leq X_i \leq M$
• 输入的所有值均为整数。

样例解释 1

满足条件的 $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

所有由 $1$ 到 $4$ 之间的整数构成的长度为 $8$ 的数列都满足条件。注意当 $X_B = B$ 时，任意两个 $B$ 之间必然包含 $B$。

由 ChatGPT 4.1 翻译