Cool Problem

The problem is not asking for the sum over completions. It asks for the sum of distinct possible values of $f$. That distinction matters; counting completions is the classic trap here, and it gets you cooked.

The first useful move is to stop trying to track the whole generating array. Define

$\Phi(z)=z^2+(x-y)z.$

For a 0 transition, $c_i=c_{i-1}+x$:

$\Phi(c_i)-\Phi(c_{i-1})=2x(c_{i-1}+x)-xy=2x c_i-xy.$

For a 1 transition, $c_i=y-c_{i-1}$:

$\Phi(c_i)-\Phi(c_{i-1})=2x(y-c_{i-1})-xy=2x c_i-xy.$

Beautifully, both cases give the same identity. Summing over $i=1\dots n$ gives

$\Phi(c_n)-\Phi(c_0)=\sum_{i=1}^{n}(2x c_i-xy).$

Since $c_0=0$ and $\Phi(0)=0$,

$c_n^2+(x-y)c_n=2x f-nxy,$

so

$f=\frac{c_n^2+(x-y)c_n+nxy}{2x}.$

That means a completed string's entire sum is determined only by its final value $c_n$. The problem becomes: find all possible final values $c_n$, map them through this formula, remove duplicates, and sum them.

Now we need a compact reachable-set DP for $c_n$.

Starting from $0$, every reachable value can be represented in one of these four forms:

$ix,\qquad ix+y,\qquad -ix,\qquad -ix+y,$

where $i\ge 0$. After at most $n$ operations, we only need $0\le i\le n$.

Maintain four bitsets:

• $A_0[i]$: value $ix$ is reachable.
• $A_1[i]$: value $ix+y$ is reachable.
• $B_0[i]$: value $-ix$ is reachable.
• $B_1[i]$: value $-ix+y$ is reachable.

Initially, $0$ is reachable, so set $A_0[0]$ and $B_0[0]$.

If the next chosen character is 0, then $c\mapsto c+x$:

$ix\to(i+1)x,$ $ix+y\to(i+1)x+y,$ $-ix\to-(i-1)x,$ $-ix+y\to-(i-1)x+y.$

So the positive-family bitsets shift left, and the negative-family bitsets shift right.

If the next chosen character is 1, then $c\mapsto y-c$:

$ix\to -ix+y,$ $ix+y\to -ix,$ $-ix\to ix+y,$ $-ix+y\to ix.$

So this operation just swaps between the four families.

There is one annoying boundary detail: $0$ has two names, $A_0[0]$ and $B_0[0]$, and $y$ has two names, $A_1[0]$ and $B_1[0]$. After every step, sync those pairs. This avoids special-casing shifts from index $0$.

For a fixed character:

• If it is not 1, apply the 0 transitions.
• If it is not 0, apply the 1 transitions.

So ? simply applies both and unions the results.

At the end, enumerate all marked states, reconstruct their represented $c_n$, compute

$\frac{c_n^2+(x-y)c_n+nxy}{2x},$

sort the resulting values, remove duplicates, and sum modulo $998244353$.

Why deduplicate after computing $f$, not only after computing $c_n$? Because the quadratic can map two different final values to the same sum. Also, the four-family representation itself can contain duplicate numeric values when $x$ and $y$ have special relationships. Sorting the final $f$ values is the blunt and correct fix.

The numerator can exceed 64-bit while computing $c_n^2$, so use __int128. The final $f$ itself fits in signed 64-bit under the constraints, but the intermediate square does not always play nice.

Complexity: each transition uses a constant number of bitset shifts and ORs over $O(n)$ bits. With word-level bitset operations, this is

$O\left(\frac{n^2}{64}\right)$

per large test in practice, and the total $n$ over all tests is $10^5$. Memory is $O(n)$ bits per bitset, i.e. tiny.