Summing Weights in a Particle Collision System

Consider a system consisting of four types of microscopic particles: A⁺, A^-, B⁺, and B^-. Initially, n A particles are arranged on a straight line. Afterwards, each particle is given an initial velocity: particles with positive charge move to the left and those with negative charge move to the right. All particles move at a constant speed and interactions between particles are ignored except when two particles collide.

When two particles collide, they bounce off and reverse their directions. In addition, they undergo a type transformation following these rules:

• If the two colliding particles have the same charge, nothing happens.
• If they have opposite charges, each particle changes into the other particle type while retaining its charge. For example, when a- and b+ collide, a- becomes b- and b+ becomes a+ (and both reverse their directions).

Since the charge of a particle determines its direction (positive goes left, negative goes right), note that throughout the entire process the direction of each particle is fixed by its charge even though its type may change. After a sufficiently long time, all left‐moving (positive) particles will be collected on the left. Define the weight of an initial arrangement as the number of B particles among those that have been collected on the left at the end.

Initially, the sign (charge) of some A particles is already determined (either + or -), while for other particles the charge is free to choose (it can be either + or -). For a given arrangement we thus have a string of length n where each character is either +, - or ? (a ? means the charge is not fixed and can be chosen arbitrarily).

Your task is to compute the sum, over all possible assignments for the free charges, of the weight defined as the number of B particles collected on the left. Since in every collision a pair of oppositely charged particles flip their types (from A to B or vice versa), a useful observation is that a particle’s final type depends on the parity of the number of collisions it experiences. Note that:

• A particle initially of type A becomes B if and only if it is involved in an odd number of collisions with particles of opposite charge.
• A collision between a left-moving (positive) particle and a right-moving (negative) particle happens if and only if the positive-charge particle is originally positioned to the right of the negative-charge particle. (Assume the particles are placed from left to right in the given order.)

Therefore, for any particle that eventually moves left (i.e. has positive charge), the number of collisions it is involved in equals the number of negatively charged particles that appear before it. It will have final type B if and only if the number of such collisions is odd.

Let the free positions be those marked with ?. For a given index j (1-indexed) which ends up as a + (either fixed or chosen in a free position), let r be the number of fixed '-' in positions 1 to j-1, and let f be the number of free positions in positions 1 to j-1. Then the total number of assignments for positions 1 to j-1 that cause an odd number of negatives is:

\(\text{ways}(j) = \begin{cases}\;2^{f-1}, & \text{if } f > 0,\\ \;1, & \text{if } f = 0 \text{ and } (r \bmod 2 = 1),\\ \;0, & \text{if } f = 0 \text{ and } (r \bmod 2 = 0).\end{cases}\)

Furthermore, if a free position is used to assign a '+' or '-' then that choice is unique in the count. Also, assignments for positions that come after index j are independent. Let T be the total number of free positions in the entire string. Then for index j, if it is fixed as '+' the number of complete assignments contributing is:

\(\text{ways}(j) \times 2^{T - f}\)

and if it is free (and is chosen to be '+') the contributing factor is:

\(\text{ways}(j) \times 2^{T - f - 1}\).

Your task is to output the sum of weights over all assignments modulo \(998\,244\,353\).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of particles. The second line contains a string of length n consisting of characters +, - and ?. A character ? indicates that the corresponding particle's charge is free to be chosen as either + or -.

outputFormat

Output one integer — the sum of the weights over all possible assignments, taken modulo \(998\,244\,353\).

sample

1
+

0

</p>