分数: 900 点
问题陈述
有一个有向图 2N 顶点和 2N-1 边缘。 顶点已编号 1, 2, \ldots, 2N,以及 i-th 边是从顶点开始的有向边 i 到顶点 i+1.
给你一个长度-2N 字符串 S = S_1 S_2 \ldots S_{2N} 组成 N W和 N Bs。
顶点 i 的颜色为白色,如果 S_i is W,如果 S_i is B.
您将执行以下一系列操作:
- 分区 2N 顶点变成 N 对,每对由一个白色顶点和一个黑色顶点组成。
- 对于每一对,添加一条从白色顶点到黑色顶点的有向边。
打印数字,模数 998244353,将顶点划分为 N 配对,使得最终图是强连接的。
关于强连通性的注释
有向图是 强连接 当且仅当可以通过跟随边从任何顶点移动到任何顶点。
约束
- 1 \le N \le 2\times 10^5
- S 是长度 2N 字符串组成 N
W和 NBs。 - N 是一个整数。
输入
输入由标准输入按以下格式给出:
N S
输出
打印数字,模数 998244353,将顶点划分为 N 配对,以便最终图是强连接的。
示例输入 1
2 BWBW
示例输出 1
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
4 BWWBWBWB
示例输出 2
0
无论如何配对顶点,都无法满足条件。
示例输入 3
9 BWWBWBBBWWBWBBWWBW
示例输出 3
240792