← 返回题目列表

AtCoder · jsc2019_qual_c

C. 细胞反转

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 2N 方块从左到右排列。给你一个长度的字符串 2N 代表每个方块的颜色。

的颜色 i从左边算起的第一个方格是黑色的,如果 i- 第一个字符 S is B,如果该字符是白色 W.

您将准确执行以下操作 N 次:选择两个不同的方块,然后反转这些方块以及它们之间的方块的颜色。这里,反转正方形的颜色就是如果它是黑色的,则将其变为白色,反之亦然。

在整个过程中,您不能选择同一个方块两次或多次。也就是说,每个方格必须被恰好选择一次。

求在过程结束时使所有方块变白的方法数量,取模 10^9+7.

两种使方块变白的方法被认为是不同的当且仅当存在 i (1 \leq i \leq N) 使得在 i-th 操作不同。

约束

  • 1 \leq N \leq 10^5
  • |S| = 2N
  • 每个字符 S is B or W.

输入

输入由标准输入按以下格式给出:

N
S

输出

打印在过程结束时使所有方块变白的方法数量,模数 10^9+7。如果没有这样的方法,则打印 0.


示例输入 1

2
BWWB

示例输出 1

4

有四种方法可以使所有方块变白,如下:

  • 选择方块 1, 3 在第一个操作中,选择 Squares 2, 4 在第二次操作中。
  • 选择方块 2, 4 在第一个操作中,选择 Squares 1, 3 在第二次操作中。
  • 选择方块 1, 4 在第一个操作中,选择 Squares 2, 3 在第二次操作中。
  • 选择方块 2, 3 在第一个操作中,选择 Squares 1, 4 在第二次操作中。

示例输入 2

4
BWBBWWWB

示例输出 2

288

示例输入 3

5
WWWWWWWWWW

示例输出 3

0