CF2189D2 Little String (Hard Version)

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

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

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

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.