P14599 CF1093F 加强版

Niko 有一个长度为 $n$ 的整数序列 $a$ 以及两个整数 $k,\text{len}$，保证 $a_i\in[1,k]\cup\{-1\}$。 求有多少种将 $a$ 中的 $-1$ 替换为 $[1,k]$ 中的整数的方式，使得 $a$ 中不存在长度为 $\text{len}$ 的连续相同区间。答案对 $10^9+7$ 取模。

第一行三个正整数 $n,k,\text{len}$。 第二行 $n$ 个整数 $a_i$。

输出一行一个数，表示合法的方案数对 $10^9+7$ 取模的结果。

对于所有数据，$1\le n,k\le2\times10^6$，$1\le\text{len}\le n$，$a_i\in[1,k]\cup\{-1\}$，输入均为整数。