CF2189D1.Little String (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, it is guaranteed that the string $s$ does not contain the character ?.

For the string $w_1w_2 \ldots w_n$, consisting of characters 0 and 1, we define $f(w)$ as the number of permutations $p_1, p_2, \ldots, p_n$ of the array $[0, 1, \ldots, n-1]$, such that for all $i$ from $1$ to $n$ the following holds:

• if $w_i = \texttt{1}$, then there exist such $1 \leq l \leq r \leq n$ that $\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$;$^{\text{∗}}$

• if $w_i = \texttt{0}$, then there do not exist such $1 \leq l \leq r \leq n$ that $\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$.

Given a string $s_1s_2 \ldots s_n$, consisting of characters 0 and 1, and a positive integer $c$. Note that in this version of the problem, the string $s$ doesn't contain ?. Consider all strings $w$ that can be obtained from $s$ by replacing all characters ? with characters 0 and 1. Find the smallest value of $f(w)$ among all such strings $w$ that is not divisible by $c$, or determine that such a string $w$ does not exist. Since the answer may be large, find it modulo $10^9+7$.

$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$.

这是该问题的简单版本。两个版本的区别在于：在本版本中，保证字符串 $s$ 不包含字符 ?。

对于由字符 0 和 1 组成的字符串 $w_1w_2 \ldots w_n$，我们定义 $f(w)$ 为数组 $[0, 1, \ldots, n-1]$ 的排列 $p_1, p_2, \ldots, p_n$ 的个数，使得对所有 $i$（从 $1$ 到 $n$）均满足以下条件：

• 若 $w_i = \texttt{1}$，则存在 $1 \leq l \leq r \leq n$，使得 $\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$；$^{\text{∗}}$

• 若 $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$ 整除的最小 $f(w)$ 值；若不存在这样的字符串 $w$，则判定其不存在。由于答案可能很大，请对 $10^9+7$ 取模输出结果。

$^{\text{∗}}$ 一组整数 $c_1, c_2, \ldots, c_k$ 的最小未出现值（MEX） 定义为不在该集合中出现的最小非负整数 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $c$ ($3 \leq n \leq 2 \cdot 10^5$, $1 \leq c \leq 10^9$) — the length of the string and the number that limits the value of the function.

The second line of each test case contains a string of length $n$, consisting of characters 0 and 1 — the string $s$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

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

每个测试用例的第二行包含一个长度为 $n$ 的字符串，由字符 0 和 1 组成 —— 即字符串 $s$。

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

For each test case, if there exists such a string $w$ that can be obtained from $s$ by replacing all characters ? with characters 0 and 1, such that $f(w)$ is not divisible by $c$, then output the minimum value of $f(w)$ among all such strings $w$. The answer should be output modulo $10^9+7$. If such a string does not exist, output $-1$.

对于每个测试用例，若存在字符串 $w$，使得 $w$ 可通过将 $s$ 中所有字符 ? 替换为字符 0 和 1 得到，且 $f(w)$ 不能被 $c$ 整除，则输出所有满足条件的字符串 $w$ 中 $f(w)$ 的最小值（答案对 $10^9+7$ 取模）。若不存在这样的字符串，则输出 $-1$。

In the second test case, there is no suitable string $w$, since $f(w)$ is always divisible by $1$.

In the third test case, we can only take $w = s$, then $f(w) = 4$, as there are exactly $4$ suitable permutations:

1. $p = [0, 2, 3, 1]$;
2. $p = [0, 3, 2, 1]$;
3. $p = [1, 2, 3, 0]$;
4. $p = [1, 3, 2, 0]$.

In the sixth test case, one can take the string $w = \mathtt{10001}$, then $f(w)$ will be equal to $12$. One of the suitable permutations is $[0, 4, 3, 2, 1]$, while, for example, the permutation $[0, 1, 2, 3, 4]$ does not fit. It can be shown that $12$ is the smallest value not divisible by $8$ that can be obtained.

在第二个测试用例中，不存在合适的字符串 $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$ 整除的最小值。