CF2189D2 Little String (Hard Version)

这是该问题的困难版本。与简单版本不同的是，在本版本中，字符串 $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 = 1$，则存在 $1 \leq l \leq r \leq n$，使得 $\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$； - 如果 $w_i = 0$，则不存在 $1 \leq l \leq r \leq n$，使得 $\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$。 现在给定一个长度为 $n$、由字符 $0$、$1$ 和 $?$ 组成的字符串 $s_1s_2\ldots s_n$，以及一个正整数 $c$。考虑所有可以通过将 $s$ 中的每个字符 $?$ 替换为 $0$ 或 $1$ 得到的字符串 $w$，请你找出所有这样字符串 $w$ 中，使得 $f(w)$ 不能被 $c$ 整除的最小 $f(w)$ 值。如果不存在这样的 $w$，则输出不存在。由于答案可能很大，请输出其模 $10^9+7$ 的结果。 $\text{∗}$ "Minimum excluded value"（最小未出现值，MEX）是指给定整数集合 $c_1, c_2, \ldots, c_k$ 中未出现的最小非负整数 $x$。

每组测试数据包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。测试用例的描述如下。 每个测试用例的第一行包含两个整数 $n$ 和 $c$（$3 \leq n \leq 2 \times 10^5$，$1 \leq c \leq 10^9$），表示字符串的长度与限制函数值的整数。 第二行包含一个长度为 $n$、由字符 $0$、$1$、$?$ 组成的字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，如果存在可通过将 $s$ 中所有 $?$ 替换成 $0$ 或 $1$ 得到的字符串 $w$，并且 $f(w)$ 不能被 $c$ 整除，则输出所有这样的 $w$ 对应的最小 $f(w)$ 值。答案需要对 $10^9+7$ 取模。如果不存在，则输出 $-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 = 10001$，此时 $f(w) = 12$。其中一个满足要求的排列是 $[0, 4, 3, 2, 1]$，而例如排列 $[0, 1, 2, 3, 4]$ 并不满足条件。可证明 $12$ 是所有不能被 $8$ 整除的 $f(w)$ 最小值。 由 ChatGPT 5 翻译