B - RGB Balls Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 ≦ N ≦ 10^5
  • |S|=3N
  • S は R, G, B のみからなり、それぞれ N 回ずつ S に登場する

入力

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

N
S

出力

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

入力例 1

3
RRRGGGBBB

出力例 1

216

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

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

入力例 2

5
BBRGRRGRGGRBBGB

出力例 2

960

Score : 800 points

Problem Statement

We have 3N colored balls with IDs from 1 to 3N. A string S of length 3N represents the colors of the balls. The color of Ball i is red if S_i is R, green if S_i is G, and blue if S_i is B. There are N red balls, N green balls, and N blue balls.

Takahashi will distribute these 3N balls to N people so that each person gets one red ball, one blue ball, and one green ball. The people want balls with IDs close to each other, so he will additionally satisfy the following condition:

  • Let a_j < b_j < c_j be the IDs of the balls received by the j-th person in ascending order.
  • Then, \sum_j (c_j-a_j) should be as small as possible.

Find the number of ways in which Takahashi can distribute the balls. Since the answer can be enormous, compute it modulo 998244353. We consider two ways to distribute the balls different if and only if there is a person who receives different sets of balls.

Constraints

  • 1 \leq N \leq 10^5
  • |S|=3N
  • S consists of R, G, and B, and each of these characters occurs N times in S.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of ways in which Takahashi can distribute the balls, modulo 998244353.

Sample Input 1

3
RRRGGGBBB

Sample Output 1

216

The minimum value of \sum_j (c_j-a_j) is 18 when the balls are, for example, distributed as follows:

  • The first person gets Ball 1, 5, and 9.
  • The second person gets Ball 2, 4, and 8.
  • The third person gets Ball 3, 6, and 7.

Sample Input 2

5
BBRGRRGRGGRBBGB

Sample Output 2

960