Little String (Hard Version)

For a permutation $p$, define $pos_x$ as the position of value $x$.

For $i<n$, a subarray has MEX $i$ exactly when it contains every value $0,1,\dots,i-1$ and does not contain $i$. Let $L_i=\min_{0\le x<i} pos_x,\qquad R_i=\max_{0\le x<i} pos_x.$ Any subarray containing all values below $i$ must contain the whole segment $[L_i,R_i]$.

So if $pos_i\in[L_i,R_i]$, every such subarray also contains $i$, and MEX $i$ is impossible. If $pos_i\notin[L_i,R_i]$, then $[L_i,R_i]$ itself contains all smaller values and avoids $i$, so MEX $i$ appears.

Thus MEX $i$ appears iff $pos_i$ becomes a new leftmost or rightmost position among $pos_0,pos_1,\dots,pos_i$.

Now count by insertion ranks. Build the relative order of $pos_0,pos_1,\dots,pos_{n-1}$ one value at a time. When inserting $pos_i$, its rank among the first $i+1$ positions can be any number from $1$ to $i+1$, and every sequence of insertion ranks maps to exactly one permutation. No hidden dependency. Nice, for once.

For $1\le i<n$:

• $w_i=1$ means the rank is $1$ or $i+1$, so there are $2$ choices;
• $w_i=0$ means the rank is one of $2,3,\dots,i$, so there are $i-1$ choices.

Also MEX $n$ always appears, because the whole permutation contains all values $0..n-1$. Therefore $w_n$ must be 1.

So for a fixed binary string $w$,

$$f(w)=\prod_{i=1}^{n-1} \begin{cases} 2,& w_i=1,\\ i-1,& w_i=0, \end{cases}$$

if $w_n=1$, and $f(w)=0$ otherwise.

Since $0$ is divisible by every positive $c$, any forced zero product is useless. If $s_1=0$ or $s_n=0$, the answer is immediately $-1$.

Now minimize the product over replacements of ?.

For each position $i<n$:

• fixed 1 contributes $2$;
• fixed 0 contributes $i-1$;
• ? lets us choose between $2$ and $i-1$.

The smallest positive choice for a ? is factor $1$ at $i=2$, and factor $2$ everywhere else. Let this minimum product be $P$.

If $P$ is not divisible by $c$, it is the answer.

Now suppose $P$ is divisible by $c$. Changing a ? can only replace the base factor by the other factor. At $i=2$, this changes $1$ to $2$, which only adds a factor of $2$. At odd $i$, replacing $2$ by $i-1$ replaces it with an even number, so no prime exponent decreases. At even $i\ge4$, replacing $2$ by odd $i-1$ decreases the exponent of prime $2$ by exactly $1$.

No move can decrease an odd prime exponent. Therefore, once $P$ is divisible by $c$, the only way to break divisibility is to reduce the power of $2$ below what $c$ requires.

Let $e$ be the exponent of $2$ in $c$, and let $v$ be the exponent of $2$ in $P$. We need $v-k<e,$ so the minimum number of useful changes is $k=v-e+1.$ If $c$ is odd, or fewer than $k$ useful positions exist, no valid string exists.

Each useful change at even ? position $i\ge4$ replaces $2$ by odd $i-1$, multiplying the product by $(i-1)/2$. These ratios increase with $i$, so the cheapest repair is taking the first $k$ such positions.

We maintain $P$ modulo $10^9+7$. For each selected repair, multiply by $i-1$ and by the modular inverse of $2$.

The algorithm factors $c$, scans the string once, checks divisibility of $P$, and possibly applies the cheapest repairs. Complexity is $O(n+\pi(\sqrt c)+m)$ per test case, where $m$ is the number of prime factors of $c$. Memory is $O(m)$.