Multithreading (Easy Version)
Contest: Codeforces Global Round 12
Difficulty rating: 2900
Tags: combinatorics, fft, math

The only difference between the two versions of the problem is that there are no updates in the easy version.

There are $$$n$$$ spools of thread placed on the rim of a circular table. The spools come in two types of thread: the first thread is black and the second thread is white.

For any two spools of the same color, you can attach them with a thread of that color in a straight line segment. Define a matching as a way to attach spools together so that each spool is attached to exactly one other spool.

Coloring is an assignment of colors (white and black) to the spools. A coloring is called valid if it has at least one matching. That is if the number of black spools and the number of white spools are both even.

Given a matching, we can find the number of times some white thread intersects some black thread. We compute the number of pairs of differently colored threads that intersect instead of the number of intersection points, so one intersection point may be counted multiple times if different pairs of threads intersect at the same point. If $$$c$$$ is a valid coloring, let $$$f(c)$$$ denote the minimum number of such intersections out of all possible matchings.

The circle above is described by the coloring bwbbbwww. After matching the spools as shown, there is one intersection between differently colored threads. It can be proven that it is the minimum possible, so $$$f(\text{bwbbbwww}) = 1$$$.

You are given a string $$$s$$$ representing an unfinished coloring, with black, white, and uncolored spools. A coloring $$$c$$$ is called $$$s$$$-reachable if you can achieve it by assigning colors to the uncolored spools of $$$s$$$ without changing the others.

A coloring $$$c$$$ is chosen uniformly at random among all valid, $$$s$$$-reachable colorings. Compute the expected value of $$$f(c)$$$. You should find it by modulo $$$998244353$$$.

We can show that the answer can be written in the form $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are relatively prime integers and $$$q\not\equiv 0\pmod{998244353}$$$. The answer by modulo $$$998244353$$$ is equal to $$$(p\cdot q^{-1})$$$ modulo $$$998244353$$$.

Input format:
The first line contains two integers $$$n$$$, $$$m$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$n$$$ is even, $$$m=0$$$) — the number of spools and updates, respectively. There are no updates in the easy version, so it is always $$$0$$$.

The second line contains a string $$$s$$$ of length $$$n$$$ — the unfinished coloring of the spools. The $$$i$$$-th character will be 'w', 'b', or '?', describing if the $$$i$$$-th spool is white, black, or uncolored, respectively.

It is guaranteed there exists at least one uncolored spool.

Output format:
Print the expected value of $$$f(c)$$$ by modulo $$$998244353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The first test corresponds closely to the image. Coloring '?' as 'w' does not create a valid coloring because the number of black spools is odd. Then the only reachable valid coloring is 'bwbbbwww' and $$$f(\text{bwbbbwww}) = 1$$$, so the expected value is $$$1$$$.

It can be shown that the expected value for the second test is $$$\frac{9}{16}$$$.

Example input:
8 0
bwbb?www

Example output:
1

Example input:
10 0
???ww?wb??

Example output:
436731905

Editorial:
Lets first solve for a given coloring, $$$c$$$, the value of $$$f(c)$$$. Let $$$B_{odd}$$$, $$$B_{even}$$$ denote the number of black spots on even positions, and odd positions respectively. We notate similarly for $$$W_{odd}$$$ and $$$W_{even}$$$.
Claim: $$$f(c) = \frac12 |B_{odd} - B_{even}|$$$.
Proof: Let's show for any coloring where $$$B_{odd} - B_{even} = 2k$$$ (the other case $$$B_{even} - B_{odd} = 2k$$$ is equivalent) we have $$$f(c)=k$$$.
1. Let's show $$$f(c)\le k$$$ with a construction of $$$k$$$ intersections. Given the condition, let's show a construction. Suppose that $$$B_{odd}\geq 1$$$ and $$$B_{even}\geq 1$$$. Then there are two adjacent positions of the same color. Connect those positions and continue to solve for the remaining spools. Eventually, there will be $$$B_{odd} = 2k$$$ and $$$W_{even} = 2k$$$ in an alternating pattern $$$\text{bwbw}\ldots\text{bwbw}$$$. It's easy to connect these to form $$$k$$$ connections.
2. Let's show $$$f(c)\ge k$$$ by proving any matching has at least $$$k$$$ intersections. First, we may assume there are no same-color intersections. If one existed, we could improve the matching, not increasing the number of different-color intersections.Now, since $$$B_{odd}-B_{even}=2k$$$, there are at least $$$k$$$ black spools on odd positions that are connected to other black spools on odd positions. Each such thread splits the other spools into two sections, each with an odd number of spools. Therefore each of these $$$k$$$ threads intersects another thread. Qed.
Now, suppose we have $$$F$$$ unfilled positions total. Say $$$F_{odd}$$$ are on odd positions and $$$F_{even}$$$ are on even positions. Let $$$x = \frac{n}{2} - W_{odd} - B_{even}$$$.
Claim: Let $$$i\equiv x\pmod 2$$$. The number of valid, $$$s$$$-reachable colorings $$$c$$$ with $$$f(c)=\frac12 |x-i|$$$ is equal to $$${F\choose i}$$$.
Proof: Suppose we have a subset of $$$i$$$ unfilled positions. For the elements of the subset, we color even positions black and odd positions white. For elements outside the subset, we color even positions white and odd positions black. Say that $$$a$$$ is the number of positions in our subset on even positions. Now, $$$B_{even}+a$$$ spools will be black on even positions, and $$$B_{odd}+F_{odd}-i+a$$$ will be black on odd positions. Then
$$$$$$f(c)=\frac12 \left|(B_{even}+a)-(B_{odd}+F_{odd}-i+a)\right|$$$$$$
$$$$$$=\frac12 |B_{even}-B_{odd}-F_{odd}+i|=\frac12 |x-i|.$$$$$$
It is clear that our mapping is a bijecetion. Qed.
Given our claims, we can write the expected value as such:
$$$$$$\frac{1}{2^F}\sum_{0\le i\le F\atop i\equiv x\pmod 2} |x-i| {{F}\choose{i}}.$$$$$$