Background

I might be wrong.

Problem Description

Consider a system consisting of four types of microscopic particles: positive/negative A particles $\text{a}^+,\text{a}^-$, and positive/negative B particles $\text{b}^+,\text{b}^-$.

At the beginning, $n$ A particles are placed on a straight line. Then, in some way, each particle is given an initial velocity so that positively charged particles move to the left, and negatively charged particles move to the right. We ignore interactions between particles, assuming that after acceleration each particle moves at a constant speed and all motion stays on the line.

When two particles collide, they bounce back and continue moving in the opposite directions. At the same time, the following transformation rules apply:

• If the two particles have the same charge, nothing happens;
• If the two particles have different charges, they both change into the other species with the same charge.

For example, when $\text{a}^-$ and $\text{b}^+$ collide, $\text{a}^-$ becomes $\text{b}^-$, and $\text{b}^+$ becomes $\text{a}^+$, and each continues moving in the opposite direction.

Define the weight of an arrangement as the number of B particles collected on the left side after a sufficiently long time.

Now, the charges (positive/negative) of some A particles have been fixed, while the remaining A particles may be positive or negative. Please compute the sum of the weights over all possible assignments.

You need to output the answer modulo $998\,244\,353$.

Input Format

Input one line containing a string $s$ of length $n$, representing the charges of the A particles from left to right. Specifically:

• If $s_i$ is +, then the $i$-th A particle is positively charged;
• If $s_i$ is -, then the $i$-th A particle is negatively charged;
• If $s_i$ is ?, then the $i$-th A particle may be positive or negative.

Output Format

Output one line with one number, representing the result modulo $998\,244\,353$.

+?+-

1

??+-?-+

11

-????-?+?--????

2523

Hint

Explanation of Sample 1

There are two possible fillings: +++- and +-+-. Their weights are $0,1$ respectively, so the final answer is $1$.

Constraints

For all testdata, it is guaranteed that $1\le n\le 2000$, and $s_i\in \{\texttt{+},\texttt{-},\texttt{?}\}$.

Translated by ChatGPT 5