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

This is the easy version of the problem. The difference between the versions is that in this version, it is guaranteed that the string $$$s$$$ does not 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 and 1, and a positive integer $$$c$$$. Note that in this version of the problem, the string $$$s$$$ doesn't contain ?. 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 and 1 — 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
9
3 3
001
3 1
111
4 100
1001
6 100
111001
6 100
111101
5 8
10001
4 100
1110
21 123456789
111000111000111000111
3 4
101
Output
-1
-1
4
96
64
12
-1
336892528
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 sixth 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.