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:

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.