题目描述

有一张包含 $N$ 个节点的图，节点编号为 $1$ 到 $N$。每个节点被染成黑色或白色。另外，已知节点 $1$ 是黑色，节点 $2$ 是白色。对于任意 $i \ne j$，存在一条从节点 $i$ 到 $j$ 的有向边，颜色为红色或蓝色。它的颜色由以下逻辑决定：

• 若 $i < j$ 且两个节点颜色相同，则边为红色。
• 若 $i < j$ 且两个节点颜色不同，则边为蓝色。
• 若 $i > j$ 且两个节点颜色相同，则边为蓝色。
• 若 $i > j$ 且两个节点颜色不同，则边为红色。

LoBren 最初最喜欢的颜色是蓝色。接着他在图上进行游走（注意，游走允许重复访问顶点和边）。行走时他遵循以下规则：

• 如果当前在节点 $1$，他最喜欢的颜色变为蓝色。
• 否则，如果当前在节点 $2$，他最喜欢的颜色变为红色。
• 然后他沿着当前节点的一条颜色与他最喜欢的颜色相同的出边移动。可以证明这样的边一定存在。
• 最后，他可以选择重复上述过程。

按顺序记录他访问过的节点，可以得到一个列表 $l_1, l_2, \ldots, l_L$。求满足以下条件的可能的列表个数（对 $10^9 + 7$ 取模）：

• 列表从节点 $1$ 开始，在节点 $2$ 结束。
• 对所有满足 $3 \le i \le N$ 的 $i$，节点 $i$ 在列表中最多出现一次。
• 对所有满足 $3 \le j \le L$ 的 $j$，有 $l_{j-2} \ne l_j$。

可以证明满足条件的列表数量是有限的。

可能还需要说明的是，“mod” 对应大多数编程语言中的 % 运算符，表示除法取余。例如，$5 \bmod 3 = 2$，$17 \bmod 4 = 1$。

输入格式

第一行输入包含一个整数 $N$。

接下来一行包含一个长度为 $N$、由字符 $\mathrm{B}$ 和 $\mathrm{W}$ 组成的字符串。若第 $i$ 个字符为 $\mathrm{B}$，则节点 $i$ 为黑色；否则为白色。保证节点 $1$ 为黑色，节点 $2$ 为白色。

输出格式

输出一行一个整数，即可能的列表数量模 $10^9 + 7$ 的结果。

4
BWWB

4

12
BWBWBBBWWBBW

3377552

提示

样例输入 #1 的输出解释

图的结构如下：

:::align{center} :::

实线表示蓝色边，虚线表示红色边。所有可能的路径为：

• $\color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}$ （从 1 沿蓝边到 2，此时在 2 最喜欢的颜色变为红）
• $\color{blue}{1}\ \color{blue}{\to}\ \color{blue}{3}\ \color{blue}{\to}\ \color{red}{\underline{2}}$
• $\color{blue}{1}\ \color{blue}{\to}\ \color{blue}{3}\ \color{blue}{\to}\ \color{blue}{4}\ \color{blue}{\to}\ \color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}$
• $\color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}\ \color{red}{\dashrightarrow}\ \color{red}{\underline{3}}\ \color{red}{\dashrightarrow}\ \color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}$

在有下划线的节点上，最喜欢的颜色为红色；在其他节点上则为蓝色。

以下表格展示了可获得的 $25$ 分的分配情况：

翻译由 DeepSeek V4 Pro 完成