[ARC100F] Colorful Sequences

## 题目描述 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$的高兴度

[problemUrl]: https://atcoder.jp/contests/arc100/tasks/arc100_d 整数 $ 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 $ で割った余りを出力せよ。

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