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