Little String (Easy Version)

Let $pos_x$ be the position of value $x$ in the permutation.

For $1 \le i < n$, a subarray has mex $i$ iff it contains every value $0,1,\dots,i-1$ and does not contain value $i$.

Look at the minimum interval covering all positions of the smaller values:

$$L_i=\min(pos_0,\dots,pos_{i-1}), \qquad R_i=\max(pos_0,\dots,pos_{i-1}).$$

Any subarray containing all values $0,\dots,i-1$ must contain the whole interval $[L_i,R_i]$.

So:

• if $pos_i \in [L_i,R_i]$, every such subarray also contains $i$, so mex $i$ is impossible;
• if $pos_i \notin [L_i,R_i]$, then the interval $[L_i,R_i]$ itself contains all smaller values and avoids $i$, so mex $i$ is possible.

Therefore, for $1 \le i < n$:

$$w_i=1 \iff pos_i \text{ is a new minimum or new maximum among } pos_0,\dots,pos_i.$$

Also, mex $n$ always exists: the full array contains all values $0,\dots,n-1$, and value $n$ does not exist. So if $s_n=0$, there are zero valid permutations. Mex $n$ is not taking requests.

Now we only need to count permutations of the sequence

$$pos_0,pos_1,\dots,pos_{n-1}$$

with this prescribed inside/outside pattern.

Use insertion ranks. When we insert $pos_i$ among the first $i+1$ positions, its rank can be any value from $1$ to $i+1$. This online rank sequence is a bijection with permutations, so we can multiply choices independently.

For $i \ge 1$:

• $pos_i$ is outside the previous min/max range iff its rank is $1$ or $i+1$, giving $2$ choices;
• $pos_i$ is inside iff its rank is one of $2,3,\dots,i$, giving $i-1$ choices.

So if $s_n=1$:

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

If any factor is $0$, then $f(s)=0$. This happens, for example, when $s_1=0$, because value $1$ cannot be inside the range of only $pos_0$. There is no room. Brutal, but clean.

In the easy version there are no question marks, so there is only one candidate string: $w=s$. Thus the answer is:

• $-1$ if $f(s)$ is divisible by $c$;
• otherwise $f(s) \bmod 10^9+7$.

We compute the product twice: once modulo $c$ to test divisibility, and once modulo $10^9+7$ for the output.

Complexity per test case is $O(n)$ time and $O(1)$ extra memory.