RGB Balls

AtCoder

IDagc037_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

3
RRRGGGBBB

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$.

Input #2

5
BBRGRRGRGGRBBGB

Output #2

API Response (JSON)

{
  "problem": {
    "name": "RGB Balls",
    "description": {
      "content": "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 $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc037_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments