题目描述

色のついたボールが $3N$ 個あり、それぞれには $1$ から $3N$ の番号がついています。 各ボールの色は長さ $3N$ の文字列 $S$ によって表されており、ボール $i$ の色は $S_i$ が R のとき赤色、G のとき緑色、B のとき青色です。 赤色のボール、緑色のボール、青色のボールはそれぞれ $N$ 個ずつあります。

高橋君はこの $3N$ 個のボールを、各人が赤、青、緑のボールを $1$ つずつ割り当てられるよう、$N$ 人の人に分配することにしました。 ただし、ボールをもらう人たちはできるだけ近い番号のボールが欲しいので、高橋君はさらに以下の条件をみたすように分配することにしました。

• $j$ 番目の人が受け取ったボールの番号を小さい順に $a_j\ <\ b_j\ <\ c_j$ とする。
• このとき $\sum_j\ (c_j-a_j)$ ができるだけ小さくなるように分配する。

高橋君がボールを分配する方法は何通りあるか求めてください。 答えは非常に大きくなることがあるので、$998244353$ で割ったあまりを求めてください。 ただし、$2$ つのボールの分配方法が異なるとは、ある人が存在して、その人が受け取ったボールの集合が異なることを指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S$

输出格式

高橋君のボールの分配方法が何通りあるかを $998244353$ で割ったあまりを出力せよ。

题目大意

题目描述

给出一个只包含$R,G,B$的字符串，保证它们三种字符出现的次数都为$n$，现在你要将这$3n$个字符分给$n$个人，使得每个人都拿到了三种字符，假设某人的三个字符在序列中的位置为$p_1,p_2,p_3$，其中$p_1≤p_2≤p_3$，那么这个人的贡献为$p_3-p_1$，问使得总贡献最小的方案数有多少，答案对$998244353$取模。

输入

输入共两行，第一行输入$n$ $(1 \leq n \leq 10^5)$，第二行输入长度为$3n$，且只含$R,G,B$三个字母，每种字符恰好$n$个的字符串。

输出

输出使得总贡献最小的方案数，对$998244353$取模。

3
RRRGGGBBB

216

5
BBRGRRGRGGRBBGB

960

提示

制約

• $1\ ≦\ N\ ≦\ 10^5$
• $|S|=3N$
• $S$ は R, G, B のみからなり、それぞれ $N$ 回ずつ $S$ に登場する

Sample Explanation 1

例えば以下のようにボールを分配したとき、$\sum_j\ (c_j-a_j)$ の値が $18$ となり最小となります。 - $1$ 番目の人にボール $1,5,9$ を渡す。 - $2$ 番目の人にボール $2,4,8$ を渡す。 - $3$ 番目の人にボール $3,6,7$ を渡す。