解题思路

核心思路

题目的限制是：

• 在任意连续的 $k$ 句话中，最多只有 $1$ 句是假话；
• 也就是任意两个假话的位置之间，距离必须至少为 $k$。

题目内容

你在玩一个 “真假话” 游戏。一共有 $n$ 句话，部分句子的真假你已经知道，其余句子未知。我们用 $1$ 表示真话、$0$ 表示假话、$-1$ 表示未知。你还知道一个规则：在任意连续的 $k$ 句话中，最多只有 $1$ 句是假话。请你计算：共有多少种不同的填充方式（把所有 $−1$ 替换为 $0$ 或 $1$）能够满足这个规则。由于答案较大，请对 $10^9+7$ 取模后输出。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T (1≤T≤2×10^5)$ 表示数据组数。此后每组测试数据依次输入：

第一行输入两个整数 $n,k (1≤k≤n≤2×10^5)$，分别表示句子数量、连续检查的窗口长度。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n$​，其中 $a_i∈${$−1,0,1$}。这里 $−1$ 表示未知，$1$ 表示真话，$0$ 表示假话。保证给出的已知信息本身不违反规则，即在任意长度为 $k$ 的连续段中，已知的假话数量至多为 $1$。

除此之外，保证单个测试文件中 $n$ 的总和不超过 $5×10^5$。

输出描述

对于每一组测试数据，新起一行输出满足条件的填充方案数，结果对 $10^9+7$ 取模。

样例1

输入

3
5 2
-1 -1 -1 -1 -1
4 3
1 -1 0 -1
6 1
1 -1 -1 -1 -1 0

输出

13
1
16

说明

第二组：$n=4,k=3$，已知第 $1$ 句为真，第 $3$ 句为假。任何长度为 $3$ 的连续段内最多 $1$ 个 0，因此第 $2$、第 $4$ 句都不能再为假，只能填为真，只有一种方案。