← 返回题目列表

Codeforces · 2189/D2

D2. 小弦(硬版)

中文机器翻译题面 查看原题

这是 硬 版本问题。版本之间的区别在于,在此版本中,字符串 $$$s$$$ 可以包含字符 ?.

对于字符串 $$$w_1w_2 \ldots w_n$$$,由字符组成 0 和 1,我们将 $$$f(w)$$$ 定义为数组 $$$[0, 1, \ldots, n-1]$$$ 的排列数 $$$p_1, p_2, \ldots, p_n$$$,这样对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 成立:

  • 如果 $$$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$$$。

给定一个字符串 $$$s_1s_2 \ldots s_n$$$,由字符组成 0, 1,和 ?和一个正整数 $$$c$$$。考虑通过替换所有字符可以从 $$$s$$$ 获得的所有字符串 $$$w$$$ ? 带有字符 0 和 1。求$$$f(w)$$$在所有这样的字符串$$$w$$$中不能被$$$c$$$整除的最小值,或者判断这样的字符串$$$w$$$不存在。由于答案可能很大,请对 $$$10^9+7$$$ 求模。

$$$^{\text{*}}$$$整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的最小排除 (MEX) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$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$$$ 的字符串,由字符组成 0, 1,和 ? — 字符串 $$$s$$$。

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

输出

对于每个测试用例,是否存在这样一个字符串$$$w$$$,可以通过替换所有字符从$$$s$$$获得 ? 带有字符 0 和 1,使得 $$$f(w)$$$ 不能被 $$$c$$$ 整除,然后输出所有此类字符串 $$$w$$$ 中 $$$f(w)$$$ 的最小值。答案应该以 $$$10^9+7$$$ 为模输出。如果这样的字符串不存在,则输出$$$-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
-1
4
2
96
64
12
-1
833286105
2

注意

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