P4785.第2题-何物为真
题目内容
你在玩一个 “真假话” 游戏。一共有 n 句话，部分句子的真假你已经知道，其余句子未知。我们用 1 表示真话、0 表示假话、−1 表示未知。你还知道一个规则：在任意连续的 k 句话中，最多只有 1 句是假话。请你计算：共有多少种不同的填充方式（把所有 −1 替换为 0 或 1）能够满足这个规则。由于答案较大，请对 109+7 取模后输出。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T (1≤T≤2×105) 表示数据组数。此后每组测试数据依次输入：
第一行输入两个整数 n,k (1≤k≤n≤2×105)，分别表示句子数量、连续检查的窗口长度。
第二行输入 n 个整数 a1,a2,…,an，其中 ai∈{−1,0,1}。这里 −1 表示未知，1 表示真话，0 表示假话。保证给出的已知信息本身不违反规则，即在任意长度为 k 的连续段中，已知的假话数量至多为 1。
除此之外，保证单个测试文件中 n 的总和不超过 5×105。
输出描述
对于每一组测试数据，新起一行输出满足条件的填充方案数，结果对 109+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 句都不能再为假，只能填为真，只有一种方案。
