Between B and B

时间限制：2s
空间限制：1024MB

题目描述

给定一个长度为 $M$ 的序列 $(X_1,X_2,\ldots,X_M)$，每个元素都在 $1$ 到 $M$ 之间。

求有多少个长度为 $N$、元素均在 $1$ 到 $M$ 之间的序列 $A=(A_1,A_2,\ldots,A_N)$ 满足下述条件，答案对 $998244353$ 取模：

• 对每个 $B=1,2,\ldots,M$，在 $A$ 中任意两个不同位置的 $B$ 之间（包含两端）都至少出现一次 $X_B$。

形式化地，对每个满足 $1\le l<r\le N$ 且 $A_l=A_r=B$ 的位置对，都存在 $m\in[l,r]$ 使 $A_m=X_B$。

输入格式

第一行输入两个整数 $M,N$。

第二行输入 $M$ 个整数 $X_1,X_2,\ldots,X_M$。

输出格式

输出合法序列数量对 $998244353$ 取模后的结果。

样例输入 1

3 4
2 1 2

样例输出 1

14

样例输入 2

4 8
1 2 3 4

样例输出 2

65536

样例输入 3

4 9
2 3 4 1

样例输出 3

628

数据范围

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