CFCF2189D2.Little String (Hard Version)

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的困难版本。与简单版本不同的是，在本版本中，字符串 $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$ 。

输入输出样例

输入#1

10
3 3
00?
3 1
???
4 100
1001
3 3
???
6 100
111001
6 100
111101
5 8
100?1
4 100
1??0
20 253034496
10001100011000??????
3 4
1?1

输出#1

说明/提示

在第二个测试用例中，没有合适的字符串 $w$ ，因为所有 $f(w)$ 都能被 $1$ 整除。

在第三个测试用例中，只能取 $w=s$ ，此时 $f(w)=4$ ，正好有 $4$ 个满足条件的排列：

$p = [0, 2, 3, 1]$ ；
$p = [0, 3, 2, 1]$ ；
$p = [1, 2, 3, 0]$ ；
$p = [1, 3, 2, 0]$ 。

在第七个测试用例中，可以取字符串 $w = 10001$ ，此时 $f(w) = 12$ 。其中一个满足要求的排列是 $[0, 4, 3, 2, 1]$ ，而例如排列 $[0, 1, 2, 3, 4]$ 并不满足条件。可证明 $12$ 是所有不能被 $8$ 整除的 $f(w)$ 最小值。

首页