#5752. 「CCO 2026」Walking on a Graph

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

译自 CCO 2026 Day2 T3「Walking on a Graph」。

有一个包含 $N$ 个节点的图，节点编号从 $1$ 到 $N$。每个节点都被染成黑色或白色。已知节点 $1$ 是黑色，节点 $2$ 是白色。对于任何满足 $i \neq j$ 的节点对，都存在一条从节点 $i$ 到 $j$ 的有向边，其颜色为红色或蓝色。边的颜色由以下逻辑确定：

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

LoBren 的初始最爱颜色是蓝色。随后他在图上进行行走（注意：行走允许重复经过顶点和边）。他在行走时遵循以下规则：

• 若他当前位于节点 $1$，他的最爱颜色变为蓝色。
• 否则，若他当前位于节点 $2$，他的最爱颜色变为红色。
• （若他位于其他节点，其最爱颜色保持不变。）
• 然后，他从当前节点出发，沿着一条与他当前最爱颜色相同的有向边移动。可以证明，这样的边一定存在。
• 最后，他可以自主选择是否重复上述过程。

通过按顺序记录他访问的节点，他得到了一个列表 $l_1, l_2, \dots, l_L$。请计算满足以下条件的可能列表的数量，结果对 $10^9 + 7$ 取模：

• 列表起始于节点 $1$，终止于节点 $2$。
• 对于所有 $3 \le i \le N$，节点 $i$ 在列表中最多出现一次。
• 对于所有 $3 \le j \le L$，满足 $l_{j - 2} \neq l_j$。

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

提示：$\bmod$ 对应于大多数编程语言中的 $\%$ 运算符，表示除法后的余数。例如，$5 \bmod 3 = 2$ 且 $17 \bmod 4 = 1$。

输入格式

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

第二行包含一个长度为 $N$ 的字符串，由字符 B 和 W 组成。若第 $i$ 个字符为 B，则节点 $i$ 为黑色；否则为白色。保证节点 $1$ 是黑色，节点 $2$ 是白色。

输出格式

在一行中输出可能列表的数量，结果对 $10^9 + 7$ 取模。

样例 1

输入

4
BWWB

输出

4

该图的结构如下：

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

在带下划线的节点处，最爱颜色为红色，其余情况下为蓝色。

样例 2

输入

12
BWBWBBBWWBBW

输出

3377552

数据范围与提示

详细子任务附加限制及分值如下表所示。