题目描述

给定整数 $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

输入

3 2 1
1

输出

9

样例 2

输入

4 2 2
1 2

输出

12

样例 3

输入

7 4 5
1 2 3 1 2

输出

17

样例 4

输入

5 4 3
1 1 1

输出

0

样例 5

输入

10 3 5
1 1 2 3 3

输出

1458

样例 6

输入

25000 400 4
3 7 31 127

输出

923966268

样例 7

输入

9954 310 12
267 193 278 294 6 63 86 166 157 193 168 43

输出

979180369

说明/提示

限制条件

• $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 翻译