AT_arc100_d [ARC100F] Colorful Sequences

给定整数 $N$、$K$，以及一个长度为 $M$ 的整数序列 $A$。 如果一个整数序列的每个元素都是 $1$ 到 $K$ 之间的整数，并且存在一个长度为 $K$ 的连续子序列，恰好包含 $1$ 到 $K$ 的每个整数各一次，则称该序列是“彩色”的。 请你统计所有长度为 $N$ 的彩色整数序列中，包含与 $A$ 完全相同的连续子序列的个数，并求这些个数的总和。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

输入以如下格式从标准输入读入。 > $N$ $K$ $M$ $A_1$ $A_2$ $\ldots$ $A_M$

请输出所有长度为 $N$ 的彩色整数序列中，包含与 $A$ 完全相同的连续子序列的个数的总和，对 $10^9+7$ 取模。

## 限制条件 - $1 \leq N \leq 25000$ - $1 \leq K \leq 400$ - $1 \leq M \leq N$ - $1 \leq A_i \leq K$ - 所有输入均为整数。 ## 样例解释 1 长度为 $3$ 的彩色整数序列有 $(1,1,2)$、$(1,2,1)$、$(1,2,2)$、$(2,1,1)$、$(2,1,2)$、$(2,2,1)$ 共 $6$ 个。对于这些序列，包含与 $A=(1)$ 完全相同的连续子序列的个数分别为 $2$、$2$、$1$、$2$、$1$、$1$。因此，这些个数的总和为 $9$，即为答案。 由 ChatGPT 4.1 翻译