D2. Маленькая строчка (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии строка $$$s$$$ может содержать символы ?.

Для строки $$$w_1w_2 \ldots w_n$$$, состоящей из символов 0 и 1, определим $$$f(w)$$$ как количество перестановок $$$p_1, p_2, \ldots, p_n$$$ массива $$$[0, 1, \ldots, n-1]$$$, что для всех $$$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$$$.

Дана строка $$$s_1s_2 \ldots s_n$$$, состоящая из символов 0, 1 и ?, и целое положительное число $$$c$$$. Рассмотрим все строки $$$w$$$, которые можно получить из $$$s$$$, заменой всех символов ? на символы 0 и 1. Найдите наименьшее значение $$$f(w)$$$ среди всех таких строк $$$w$$$, не делящееся на $$$c$$$, или определите, что такой строки $$$w$$$ нет. Так как ответ может быть большим, найдите его по модулю $$$10^9+7$$$.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$, то выведите минимальное значение $$$f(w)$$$ среди всех таких строк $$$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$$$, которое можно получить.