AT_arc186_e.[ARC186E] Missing Subsequence

给定一个由 $1,\dots,K$ 组成、长度为 $M$ 的整数序列 $(X_1,\dots,X_M)$。

请计算满足以下条件的长度为 $N$ 的整数序列 $(A_1,\dots,A_N)$（每个元素均为 $1,\dots,K$）的个数，并将结果对 $998244353$ 取模后输出。

• 在所有由 $1,\dots,K$ 组成、长度为 $M$ 的整数序列中，只有 $(X_1,\dots,X_M)$ 不能作为 $(A_1,\dots,A_N)$ 的（不要求连续的）子序列。

输入通过标准输入按以下格式给出。

$N$ $M$ $K$ $X_1$ $X_2$ $\dots$ $X_M$

请输出满足条件的序列数量，对 $998244353$ 取模后的结果。

限制条件

• $2\leq M,K \leq N \leq 400$
• $1\leq X_i \leq K$
• 所有输入均为整数

样例解释 1

以下 $4$ 种序列满足条件：

• $(2,\ 3,\ 1,\ 2,\ 3)$
• $(2,\ 3,\ 1,\ 3,\ 2)$
• $(3,\ 2,\ 1,\ 2,\ 3)$
• $(3,\ 2,\ 1,\ 3,\ 2)$

由 ChatGPT 4.1 翻译