AT_jsc2019_qual_c.Cell Inversion

有 $2N$ 个格子从左到右排成一行，给定一个长度为 $2N$ 的字符串 $S$，表示每个格子的颜色。

从左起第 $i$ 个格子的颜色由 $S$ 的第 $i$ 个字符决定，如果是 B，则为黑色，如果是 W，则为白色。

你需要进行恰好 $N$ 次操作。每次操作选择两个不同的格子，将这两个格子及它们之间所有格子的颜色全部反转（黑变白，白变黑）。

在所有操作过程中，每个格子只能被选择一次，也就是说，每个格子恰好被选中一次。

请计算，经过 $N$ 次操作后，所有格子都变成白色的方案数。答案对 $10^9+7$ 取模。如果不存在这样的方案，请输出 $0$。

这里，如果存在某个 $i$ $(1 \leq i \leq N)$，第 $i$ 次操作所选的两个格子的组合不同，则认为两种方案不同。

输入从标准输入读入，格式如下：

$N$ $S$

输出经过 $N$ 次操作后所有格子都变成白色的方案数，对 $10^9+7$ 取模。如果不存在这样的方案，则输出 $0$。

限制条件

• $1 \leq N \leq 10^5$
• $|S| = 2N$
• $S$ 的每个字符都是 B 或 W。

样例解释 1

将所有格子变成白色的方案有如下 $4$ 种：

• 第一次操作选择第 $1$ 和第 $3$ 个格子，第二次操作选择第 $2$ 和第 $4$ 个格子。
• 第一次操作选择第 $2$ 和第 $4$ 个格子，第二次操作选择第 $1$ 和第 $3$ 个格子。
• 第一次操作选择第 $1$ 和第 $4$ 个格子，第二次操作选择第 $2$ 和第 $3$ 个格子。
• 第一次操作选择第 $2$ 和第 $3$ 个格子，第二次操作选择第 $1$ 和第 $4$ 个格子。

由 ChatGPT 4.1 翻译