A16560 | Little String (Easy Version)

这是该问题的简单版本。不同之处在于，在本版本中，字符串 $s$ 保证不包含字符 ?。

对于由 $0$ 和 $1$ 组成的字符串 $w_1w_2 \ldots w_n$，我们定义 $f(w)$ 为数组 $[0, 1, \ldots, n-1]$ 的所有排列 $p_1, p_2, \ldots, p_n$ 的个数，满足对于所有 $1 \leq i \leq n$，都有：

- 如果 $w_i = \texttt{1}$，则存在 $1 \leq l \leq r \leq n$，使得 $\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$；
- 如果 $w_i = \texttt{0}$，则不存在 $1 \leq l \leq r \leq n$，使得 $\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$。

已知一个由字符 $0$ 和 $1$ 组成的字符串 $s_1s_2 \ldots s_n$，以及一个正整数 $c$。注意，在本版本的问题中，字符串 $s$ 不包含 ?。考虑所有可以通过将 $s$ 中的 ? 替换成 $0$ 或 $1$ 得到的字符串 $w$，找到所有这样的字符串 $w$ 中 $f(w)$ 不被 $c$ 整除的最小值，或者判断是否不存在这样的字符串 $w$。由于答案可能很大，要求输出对 $10^9+7$ 取模的结果。

注：$\operatorname{mex}$（最小未出现数）指在一组整数 $c_1, c_2, \ldots, c_k$ 中未出现的最小非负整数 $x$。

每个测试点包含多组测试用例。第一行包含整数 $t$，表示测试用例数量（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $c$（$3 \leq n \leq 2 \cdot 10^5$，$1 \leq c \leq 10^9$）——字符串的长度，以及函数值的限制数。

第二行包含一个长度为 $n$ 的字符串 $s$，只由字符 $0$ 和 $1$ 组成。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果存在某个由 $s$ 替换 ? 得到的字符串 $w$，使得 $f(w)$ 不被 $c$ 整除，则输出所有这些 $w$ 中 $f(w)$ 的最小值。答案对 $10^9+7$ 取模。如果不存在这样的 $w$，则输出 $-1$。