题目内容

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，其中每个 $a_i \in \{-1, 0, 1\}$。

每个位置的含义如下：

• -1 表示该位置的值尚未确定；
• 0 或 1 表示该位置已经被固定为对应的值。

你需要将所有 -1 替换为 0 或 1，使得最终的序列满足：在任意长度为 $k$ 的连续子数组中，值为 0 的元素个数不超过 1。

请计算有多少种不同的填充方案。由于答案可能很大，你需要输出对 $10^9+7$ 取模后的结果。

约束条件

• 测试数据组数 $T$ 满足 $1 \le T \le 2 \times 10^5$；
• 对于每组数据，$1 \le k \le n \le 2 \times 10^5$；
• 所有测试数据的 $n$ 之和不超过 $5 \times 10^5$；
• 给定的初始序列已经满足规则，即任意长度为 $k$ 的连续子数组中已知的 0 的个数不超过 1。

输入描述

第一行包含一个整数 $T \ (1 \le T \le 2 \times 10^5)$，表示测试数据的组数。 接下来对于每组测试数据，按照以下格式输入： 第一行包含两个整数 $n, k \ (1 \le k \le n \le 2 \times 10^5)$，分别表示序列的长度和检查窗口的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，每个整数取值于 $\{-1, 0, 1\}$，含义如上所述。

保证所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示合法的填充方案数对 $10^9+7$ 取模的结果。

样例1

输入

1
1 1
-1

输出

2

说明

序列只有一个元素，且窗口长度 $k=1$。由于任意长度为 1 的子数组内 0 的个数不能超过 1，该位置填 0 或 1 均满足条件（0 的个数分别为 1 和 0）。因此有两种方案。

样例2

输入

1
3 2
-1 0 -1

输出

1

说明

第二个位置已固定为 0。由于 $k=2$，任意相邻两个位置组成的窗口内最多只能有一个 0。因此第一个位置必须填 1（否则窗口 $[1,2]$ 将有两个 0），第三个位置也必须填 1（否则窗口 $[2,3]$ 将有两个 0）。唯一方案为 $1, 0, 1$，方案数为 1。

样例3

输入

3
2 2
-1 -1
5 3
0 -1 -1 -1 -1
3 2
1 -1 1

输出

3
3
2

说明

第一组：$n=2, k=2$，全为 -1。合法序列中不能出现两个 0 相邻。因此所有不含连续两个 0 的长度为 2 的序列均合法：$0,1$；$1,0$；$1,1$。共 3 种。

第二组：$n=5, k=3$，已知第一位是 0。因为任意两个 0 距离必须 $\ge 3$，下一个 0 最早可以出现在第 4 位。前三位必须为 1（第 1 位已为 0，第 2,3 位填 0 会违反距离限制）。第 4 位可填 0 或 1；第 5 位若第 4 位填 0 则只能填 1，否则可自由填 0 或 1。枚举合法序列：$0,1,1,0,1$；$0,1,1,1,0$；$0,1,1,1,1$。共 3 种。

第三组：$n=3, k=2$，已知两端为 1。中间 -1 填 0 或 1 均不违反长度为 2 的窗口限制（若填 0，两端窗口各有一个 0）。因此有 $1,0,1$ 和 $1,1,1$ 两种方案，方案数为 2。