AT_arc100_d [ARC100F] Colorful Sequences

[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/A

N/A

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