题目描述

给定两个整数 $n,k$，以及一个长度为 $m$ 的整数序列 $a$，其中 $1≤a_i≤k$。

如果一个由 $1…k$ 组成的整数序列中，存在一个长度为 $k$ 的连续子序列，满足这 $k$ 个数字在子序列中都出现过，那这个序列就被称为“彩色序列”。

对于一个“彩色序列”，我们可以计算出 $a$ 作为它的连续子序列的出现次数（出现位置可以重叠）。而你需要做的，就是计算出对于所有长度为 $n$ 的彩色序列，这个出现次数的和是多少。答案对 $10^9+7$ 取模。

输入格式

第一行包含三个整数：$n,k,m$；

第二行包含 $m$ 个整数：$a_1,a_2,…,a_m$。

输出格式

一行，一个整数，代表答案。

样例 #1

样例输入 #1

3 2 1
1

样例输出 #1

9

样例 #2

样例输入 #2

10 3 5
1 1 2 3 3

样例输出 #2

1458

提示

对于 $40\%$ 的数据，$n≤1000,k≤4$；

对于剩余 $60\%$ 的数据，$n≤25000,k≤400$；

对于所有数据，$1≤m≤n,1≤a_i≤k$。

特别地，在上述数据中，恰好有一半数据满足：序列 $a$ 中的所有数字互不相同。