题目的限制是:
你在玩一个 “真假话” 游戏。一共有 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 取模。
输入
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 句都不能再为假,只能填为真,只有一种方案。