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$$$.

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:

$$$p = [0, 2, 3, 1]$$$;
$$$p = [0, 3, 2, 1]$$$;
$$$p = [1, 2, 3, 0]$$$;
$$$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.

Little String (Hard Version)

Examples