Cell Inversion

AtCoder

IDjsc2019_qual_c

Time2000ms

Memory256MB

Difficulty—

There are $2N$ squares arranged from left to right. You are given a string of length $2N$ representing the color of each of the squares. The color of the $i$\-th square from the left is black if the $i$\-th character of $S$ is `B`, and white if that character is `W`. You will perform the following operation exactly $N$ times: choose two distinct squares, then invert the colors of these squares and the squares between them. Here, to invert the color of a square is to make it white if it is black, and vice versa. Throughout this process, you cannot choose the same square twice or more. That is, each square has to be chosen exactly once. Find the number of ways to make all the squares white at the end of the process, modulo $10^9+7$. Two ways to make the squares white are considered different if and only if there exists $i$ $(1 \leq i \leq N)$ such that the pair of the squares chosen in the $i$\-th operation is different. ## Constraints * $1 \leq N \leq 10^5$ * $|S| = 2N$ * Each character of $S$ is `B` or `W`. ## Input Input is given from Standard Input in the following format: $N$ $S$ [samples]

Samples

Input #1

2
BWWB

Output #1

4

There are four ways to make all the squares white, as follows:

*   Choose Squares $1, 3$ in the first operation, and choose Squares $2, 4$ in the second operation.
*   Choose Squares $2, 4$ in the first operation, and choose Squares $1, 3$ in the second operation.
*   Choose Squares $1, 4$ in the first operation, and choose Squares $2, 3$ in the second operation.
*   Choose Squares $2, 3$ in the first operation, and choose Squares $1, 4$ in the second operation.

Input #2

4
BWBBWWWB

Output #2

Input #3

5
WWWWWWWWWW

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Cell Inversion",
    "description": {
      "content": "There are $2N$ squares arranged from left to right. You are given a string of length $2N$ representing the color of each of the squares. The color of the $i$\\-th square from the left is black if the $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "jsc2019_qual_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $2N$ squares arranged from left to right. You are given a string of length $2N$ representing the color of each of the squares.\nThe color of the $i$\\-th square from the left is black if the $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments