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

输入 #1

3 2 1
1

输出 #1

9

输入输出样例 #2

输入 #2

4 2 2
1 2

输出 #2

12

输入输出样例 #3

输入 #3

7 4 5
1 2 3 1 2

输出 #3

17

输入输出样例 #4

输入 #4

5 4 3
1 1 1

输出 #4

0

输入输出样例 #5

输入 #5

10 3 5
1 1 2 3 3

输出 #5

1458

输入输出样例 #6

输入 #6

25000 400 4
3 7 31 127

输出 #6

923966268

输入输出样例 #7

输入 #7

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

输出 #7

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$，即为答案。

• 子任务1（10 分）：N ≤ 9, K ≤ 4。
• 子任务2（20 分）：N ≤ 200, K ≤ 30。
• 子任务3（K 很小，N 很大）（20 分）：K ≤ 8, N ≤ 25000。
• 子任务4（模式串短）（25 分）：M ≤ 20, N ≤ 25000, K ≤ 400。
• 子任务5（全约束）（25 分）：N ≤ 25000, K ≤ 400。