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