分数: 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
BorW.
输入
输入由标准输入按以下格式给出:
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