#424. AGC037 B - RGB Balls

AGC037 B - RGB Balls

题目描述

33 种球,分别标记为 RGB。每种球各有 NN 个,这 3N3 \cdot N 个球排成一行编号从 113N3 \cdot N

用一个字符串 SS 来表示这些球的颜色。

现在将这 3N3 \cdot N 个球分为 NN 组,使得每一组中三种球都恰有一个。并且满足如下条件:

  • aj<bj<cja_j \lt b_j \lt c_j 是这一组球按升序排列的编号。
  • 然后,sumjcjajsum_{j}{c_j - a_j} 应该尽可能小

问有多少种不同的分组方式,(答案对 $$998244353$ 取模),使得分组的总代价最小(两种方式被考虑为不同当且仅当至少有一个组中的球的集合不同)。

输入格式

  • 第一行 一个整数 NN
  • 第二行 一个字符串 SS

输出格式

  • 输出方式个数对 998244353998244353 取模的结果

样例

Sample Input 1

3
RRRGGGBBB

Sample Output 1

216

此样例最小的 jcjaj\sum_j{c_j - a_j}1818,例如按以下方式分配

  • 第一组分配球 11, 5599
  • 第二组分配球 22, 4488
  • 第三组分配球 33, 6677

Sample Input 2

5
BBRGRRGRGGRBBGB

Sample Output 2

962

数据范围与提示

  • 1n1051 \le n \le 10^5
  • S=3N|S| = 3N
  • SS 包含 RGB这三种字符,每一种字符在 SS 中出现 NN 次。