Perfect Cut

Do not try to count valid cuts directly. A string can have many valid cuts, so that path turns into duplicated-counting sludge fast. Instead, characterize the strings that have no valid cut.

Let the completed binary string be $x_1x_2\ldots x_n$.

For a cut after position $k$, the prefix is $x_1\ldots x_k$ and the suffix starts at $x_{k+1}$. The condition is:

$x_i \ge x_{k+i}$

for all compared positions $i$.

Since characters are only $0$ and $1$, the only bad compared pair is:

$0 \ge 1$

Everything else works: $0 \ge 0$, $1 \ge 0$, and $1 \ge 1$.

Key claim: a binary string is not perfect iff it is exactly

$011\ldots1.$

Why every other string is perfect

There are two cases.

First, if $x_1=1$, use the cut after position $n-1$. Then only one pair is compared: $x_1$ with $x_n$. Since $x_1=1$, we have $1 \ge x_n$, so the cut works.

Now suppose $x_1=0$.

If there is another zero somewhere after the first position, let $j$ be the first such position:

$j>1, \quad x_j=0,$

and there is no zero among positions $2,3,\ldots,j-1$.

So all those middle characters are $1$.

Cut after position $k=j-1$.

The comparisons are between:

$x_i \quad \text{and} \quad x_{j-1+i}.$

For $i=1$, this is:

$x_1 \ge x_j,$

which is:

$0 \ge 0,$

so it is fine.

For every compared $i\ge 2$, the prefix character $x_i$ lies in positions $2\ldots j-1$. By the choice of $j$, all of those are $1$. A prefix $1$ can dominate anything, so every remaining compared pair is also fine.

So if the string starts with $0$ but contains any later $0$, it is perfect.

Why $011\ldots1$ is not perfect

If the string is $011\ldots1$, then for every cut after position $k$, the first compared pair is:

$x_1 \ge x_{k+1}.$

Here $x_1=0$, and since $k+1\ge 2$, we have $x_{k+1}=1$. So every cut starts with:

$0 \ge 1,$

which fails instantly. Brutal, but clean.

So the entire problem collapses to this:

• every completion is perfect;
• except possibly the single completion $011\ldots1$.

Counting with question marks

Let $q$ be the number of question marks in $s$. There are

$2^q$

possible completions total.

We subtract $1$ only if the bad string $011\ldots1$ can actually be formed from $s$.

That requires:

• position $1$ is not fixed to 1;
• no position from $2$ to $n$ is fixed to 0.

If both are true, exactly one completion is bad: set the first character to $0$ and every later unknown to $1$.

So:

$\text{answer}=2^q-[011\ldots1\text{ is compatible}] \pmod{998244353}.$

Implementation is just one scan. Count question marks, check whether any fixed zero appears after the first character, and subtract the bad completion if needed. Complexity is $O(n)$ per test case, with total $O(\sum n)$ over all tests.