CF2189D1 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$。

在第二个测试用例中，不存在合适的字符串 $w$，因为 $f(w)$ 总是能被 $1$ 整除。 在第三个测试用例中，只能取 $w=s$，此时 $f(w)=4$，有恰好 $4$ 个符合条件的排列： 1. $p = [0, 2, 3, 1]$； 2. $p = [0, 3, 2, 1]$； 3. $p = [1, 2, 3, 0]$； 4. $p = [1, 3, 2, 0]$。 在第六个测试用例中，可以取 $w = \mathtt{10001}$，此时 $f(w)=12$。其中有一种符合条件的排列为 $[0,4,3,2,1]$，而排列 $[0,1,2,3,4]$ 则不符合要求。可以证明 $12$ 是所有不能被 $8$ 整除的 $f(w)$ 最小值。 由 ChatGPT 5 翻译