分数: 800 点
问题陈述
我们有 3N 彩色球,其 ID 来自 1 to 3N。
一个字符串 S 长度 3N 代表球的颜色。球的颜色 i 为红色,如果 S_i is R,如果为绿色 S_i is G,如果 S_i is B。有 N 红球, N 绿球,以及 N 蓝色球。
高桥将分发这些 3N 球到 N 人,以便每人获得一颗红球、一颗蓝球和一颗绿球。 人们想要ID彼此靠近的球,所以他还要满足以下条件:
- 让 a_j < b_j < c_j 是接收者收到的球的 ID j- 按升序排列的第一个人。
- 然后, \sum_j (c_j-a_j) 应尽可能小。
求高桥分配球的方式数。由于答案可能很大,因此对它进行模计算 998244353。 当且仅当一个人收到不同组的球时,我们才会考虑两种不同的球分配方式。
约束
- 1 \leq N \leq 10^5
- |S|=3N
- S 包括
R,G,和B,并且每个字符都出现 N 次 S.
输入
输入由标准输入按以下格式给出:
N S
输出
打印高桥可以分配球的方式数,模 998244353.
示例输入 1
3 RRRGGGBBB
示例输出 1
216
的最小值 \sum_j (c_j-a_j) is 18 例如,当球分布如下时:
- 第一个人获得球 1, 5,和 9.
- 第二个人得到球 2, 4,和 8.
- 第三人获得球 3, 6,和 7.
示例输入 2
5 BBRGRRGRGGRBBGB
示例输出 2
960