配点 : $800$ 点

問題文

色のついたボールが $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$ つのボールの分配方法が異なるとは、ある人が存在して、その人が受け取ったボールの集合が異なることを指します。

制約

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

入力

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

$N$

$S$

出力

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

3
RRRGGGBBB

216

例えば以下のようにボールを分配したとき、$\sum_j (c_j-a_j)$ の値が $18$ となり最小となります。

• $1$ 番目の人にボール $1,5,9$ を渡す。
• $2$ 番目の人にボール $2,4,8$ を渡す。
• $3$ 番目の人にボール $3,6,7$ を渡す。

5
BBRGRRGRGGRBBGB

960