D2. Little String (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, the string $$$s$$$ can contain the character ?.

For the string $$$w_1w_2 \ldots w_n$$$, consisting of characters 0 and 1, we define $$$f(w)$$$ as the number of permutations $$$p_1, p_2, \ldots, p_n$$$ of the array $$$[0, 1, \ldots, n-1]$$$, such that for all $$$i$$$ from $$$1$$$ to $$$n$$$ the following holds:

  • if $$$w_i = \texttt{1}$$$, then there exist such $$$1 \leq l \leq r \leq n$$$ that $$$\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$$$;$$$^{\text{∗}}$$$

  • if $$$w_i = \texttt{0}$$$, then there do not exist such $$$1 \leq l \leq r \leq n$$$ that $$$\operatorname{mex}([p_l, p_{l+1}, \ldots, p_r]) = i$$$.

Given a string $$$s_1s_2 \ldots s_n$$$, consisting of characters 0, 1, and ?, and a positive integer $$$c$$$. Consider all strings $$$w$$$ that can be obtained from $$$s$$$ by replacing all characters ? with characters 0 and 1. Find the smallest value of $$$f(w)$$$ among all such strings $$$w$$$ that is not divisible by $$$c$$$, or determine that such a string $$$w$$$ does not exist. Since the answer may be large, find it modulo $$$10^9+7$$$.

$$$^{\text{∗}}$$$The minimum excluded (MEX) of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — the length of the string and the number that limits the value of the function.

The second line of each test case contains a string of length $$$n$$$, consisting of characters 0, 1, and ? — the string $$$s$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, if there exists such a string $$$w$$$ that can be obtained from $$$s$$$ by replacing all characters ? with characters 0 and 1, such that $$$f(w)$$$ is not divisible by $$$c$$$, then output the minimum value of $$$f(w)$$$ among all such strings $$$w$$$. The answer should be output modulo $$$10^9+7$$$. If such a string does not exist, output $$$-1$$$.

Example
Input
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
Output
-1
-1
4
2
96
64
12
-1
833286105
2
Note

In the second test case, there is no suitable string $$$w$$$, since $$$f(w)$$$ is always divisible by $$$1$$$.

In the third test case, we can only take $$$w = s$$$, then $$$f(w) = 4$$$, as there are exactly $$$4$$$ suitable permutations:

  1. $$$p = [0, 2, 3, 1]$$$;
  2. $$$p = [0, 3, 2, 1]$$$;
  3. $$$p = [1, 2, 3, 0]$$$;
  4. $$$p = [1, 3, 2, 0]$$$.

In the seventh test case, one can take the string $$$w = \mathtt{10001}$$$, then $$$f(w)$$$ will be equal to $$$12$$$. One of the suitable permutations is $$$[0, 4, 3, 2, 1]$$$, while, for example, the permutation $$$[0, 1, 2, 3, 4]$$$ does not fit. It can be shown that $$$12$$$ is the smallest value not divisible by $$$8$$$ that can be obtained.