题目描述

整数 $N$ と $K$、そして長さ $M$ の整数列 $A$ が与えられます。

各要素が $1$ 以上 $K$ 以下の整数である整数列がカラフルであるとは、 その整数列の長さ $K$ の連続する部分列であって、$1$ から $K$ までの整数を $1$ 個ずつ含むものが存在することを意味します。

すべての長さ $N$ のカラフルな整数列について、その連続する部分列であって $A$ に一致するものの個数を数えて、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すべての長さ $N$ のカラフルな整数列について、その連続する部分列であって $A$ に一致するものの個数を数えて、 その総和を $10^9+7$ で割った余りを出力せよ。

题目大意

题目描述

Lin要过生日了，Puro想送他一个$N$层的蛋糕作为礼物，但是Puro正在纠结奶油的颜色

Puro有$K$种不同的奶油，每一层蛋糕都能涂上其中一种，但是要让他们俩同时满意是个问题，具体来说是这样的：

• 如果存在连续$K$层蛋糕，包含了所有$K$种奶油，那么这个蛋糕就是Puro最喜欢的“彩虹蛋糕”
• 同时，对任意连续$M$层蛋糕，如果它们所使用的奶油顺序刚好满足一个长度为$M$的序列$A$，那么Lin就会有$1$的高兴度（两个出现的$A$可以部分重叠）

现在问Puro能够做出的所有“彩虹蛋糕”的高兴度之和为多少？

答案对$(10^9+7)$取模

如果你答对了，Dr.K将送你一本字帖

说明/提示

$\begin{array}{l}1\le N\le 25000\\1\le K\le 400\\1\le M\le N\\1\le A_i\le K\end{array}$

样例1解释

有$(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1)$总共$6$种“彩虹蛋糕”，它们分别能产生$2,2,1,2,1,1$的高兴度，因此答案为$2+2+1+2+1+1=9$的高兴度

3 2 1
1

9

4 2 2
1 2

12

7 4 5
1 2 3 1 2

17

5 4 3
1 1 1

0

10 3 5
1 1 2 3 3

1458

25000 400 4
3 7 31 127

923966268

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$
• 入力はすべて整数である。

Sample Explanation 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$ が答えになります。