题目描述

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$ 取模的结果。

5 2 3
1 -1 1 -1 2

2

6 3 2
1 1 -1 -1 -1 -1

0

10 42 7
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

989891925

提示

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