题目描述

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$的高兴度