CF1450H1.Multithreading (Easy Version)

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$.

两个版本的问题唯一区别在于：简单版本中没有更新操作。

有 $n$ 个线轴放置在一个圆形桌子的边缘。线轴上缠绕着两种颜色的线：第一种为黑色，第二种为白色。

对于任意两个同色的线轴，你可以用该颜色的线以一条直线段将它们连接起来。定义一个匹配为一种连接方式，使得每个线轴恰好与另一个线轴相连。

染色方案指为所有线轴分配颜色（白色或黑色）的一种方案。若某染色方案至少存在一个匹配，则称其为合法的。换言之，当且仅当黑色线轴数量与白色线轴数量均为偶数时，该染色方案是合法的。

给定一个匹配，我们可以统计其中白色线段与黑色线段相交的次数。我们统计的是不同颜色线段对的相交对数，而非交点个数；因此，若多个不同颜色线段对在同一点相交，该交点会被重复计数多次。若 $c$ 是一个合法染色方案，记 $f(c)$ 为在所有可能匹配中，此类相交对数的最小值。

上图圆周对应染色方案 bwbbbwww。按图中所示方式进行匹配后，存在 1 对不同颜色线段相交。可以证明这是最小可能值，故 $f(\text{bwbbbwww}) = 1$。

你将得到一个字符串 $s$，它表示一个未完成的染色方案，其中包含黑色、白色和未染色的线轴。若染色方案 $c$ 可通过仅对 $s$ 中未染色的线轴赋色（其余位置颜色保持不变）而得到，则称 $c$ 是 $s$-可达的。

在所有合法且 $s$-可达的染色方案中，随机均匀地选取一个染色方案 $c$。请计算 $f(c)$ 的期望值（Expected value）。答案需对 $998244353$ 取模。

可以证明，该答案可表示为最简分数 $\frac{p}{q}$，其中 $p$ 与 $q$ 互质，且 $q \not\equiv 0 \pmod{998244353}$。所求答案即 $(p \cdot q^{-1}) \bmod 998244353$。

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.

第一行包含两个整数 $n$、$m$（$2\le n\le 2\cdot 10^5$，$n$ 为偶数，$m=0$）—— 分别表示线轴的数量和更新操作的数量。在简单版本中没有更新操作，因此 $m$ 恒为 $0$。

第二行包含一个长度为 $n$ 的字符串 $s$ —— 表示线轴的未完成染色状态。其中第 $i$ 个字符为 'w'、'b' 或 '?'，分别表示第 $i$ 个线轴为白色、黑色或尚未染色。

保证至少存在一个尚未染色的线轴。

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

以模 $998244353$ 输出 $f(c)$ 的期望值。

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}$.

第一个测试用例与图片高度对应。将 '?' 染成 'w' 无法得到合法染色，因为黑色线轴的数量为奇数。因此唯一可达的合法染色是 'bwbbbwww'，且 $f(\text{bwbbbwww}) = 1$，故期望值为 $1$。

可以证明第二个测试用例的期望值为 $\frac{9}{16}$。