题目描述

给定整数$N, K$以及长度为$M$的整数序列$A$。

如果存在长度为$K$的连续子序列，其中包含了$1$到$K$之间（包括$1$和$K$）的每个整数恰好一次，那么整数序列被称为“多彩”的。

对于长度为$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$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $K$ $M$ $A_1$ $A_2$ $...$ $A_M$

输出

对于长度为$N$的每个多彩整数序列，计算与$A$相符的连续子序列的数量，然后打印所有数量的和，结果对$10^9+7$取模。

示例输入 1

3 2 1
1

示例输出 1

9

长度为$3$的多彩整数序列有$6$个：$(1,1,2)$，$(1,2,1)$，$(1,2,2)$，$(2,1,1)$，$(2,1,2)$和$(2,2,1)$。这些序列中与$A=(1)$相符的连续子序列的数量分别为：$2$，$2$，$1$，$2$，$1$和$1$。因此，答案是它们的和，即$9$。

示例输入 2

4 2 2
1 2

示例输出 2

12

... ...