P16906 [CCO 2026] Walking on a Graph

有一张包含 $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$ 的结果。

**样例输入 #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{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$ 分的分配情况： | 分值 | $N$ 的范围 | 额外限制 | |:-:|:-:|:-:| | $1$ 分 | $3 \le N \le 8$ | 无。 | | $3$ 分 | $3 \le N \le 20$ | 无。 | | $4$ 分 | $3 \le N \le 50$ | 恰好存在 $1$ 个黑色节点。 | | $4$ 分 | ^ | 存在一个整数 $i$（$2 \le i \le N$），使得区间 $[2, i]$ 内的每个节点均为白色，其余节点均为黑色。 | | $6$ 分 | ^ | 黑色节点不超过 $5$ 个。 | | $7$ 分 | ^ | 无。 | 翻译由 DeepSeek V4 Pro 完成