AT_arc196_c.[ARC196C] Strongly Connected

有一个包含 $2N$ 个顶点和 $2N-1$ 条边的有向图。顶点编号为 $1, 2, \ldots, 2N$，第 $i$ 条边是从顶点 $i$ 指向顶点 $i+1$ 的有向边。

给定一个由 $N$ 个 W 和 $N$ 个 B 组成的长度为 $2N$ 的字符串 $S = S_1S_2\ldots S_{2N}$。如果 $S_i$ 是 W，则顶点 $i$ 被涂成白色；如果 $S_i$ 是 B，则顶点 $i$ 被涂成黑色。

你需要进行如下操作：

• 将 $2N$ 个顶点分成 $N$ 对，每对包含一个白色顶点和一个黑色顶点。
• 对于每一对，添加一条从白色顶点指向黑色顶点的有向边。

请计算有多少种分组方式，使得最终得到的图是强连通的。将答案对 $998244353$ 取模后输出。

强连通的定义：有向图是强连通的，当且仅当对于图中的任意两个顶点，都存在一条从一个顶点到另一个顶点的有向路径。

输入以如下格式从标准输入读入：

$N$ $S$

请输出在操作中将顶点分为 $N$ 对的所有方式中，使最终得到的图是强连通的方式数。答案对 $998244353$ 取模。

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $S$ 是由 $N$ 个 W 和 $N$ 个 B 组成的长度为 $2N$ 的字符串
• $N$ 是整数

样例解释 1

顶点 $2, 4$ 是白色，顶点 $1, 3$ 是黑色。用 $(u, v)$ 表示从顶点 $u$ 指向顶点 $v$ 的边。如果将顶点分为 $(2,1), (4,3)$ 这两对，则最终图中存在的边为 $(1,2), (2,3), (3,4), (2,1), (4,3)$。此时，例如无法从顶点 $3$ 经过若干条边到达顶点 $1$，因此该图不是强连通的。如果分为 $(2,3), (4,1)$ 这两对，则最终图中存在的边为 $(1,2), (2,3), (3,4), (2,3), (4,1)$。此时该图是强连通的。因此满足条件的分组方式有 $1$ 种。

样例解释 2

无论如何分组，都无法满足条件。

由 ChatGPT 4.1 翻译