walk

题目描述

有一个包含 $N$ 个节点的图，节点编号为 $1,2,\dots,N$。每个节点被染成黑色或白色，其中节点 $1$ 为黑色，节点 $2$ 为白色。

对于任意两个不同的节点 $i,j$，都有一条从节点 $i$ 到节点 $j$ 的有向边。边的颜色按以下规则确定：

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

LoBren 最喜欢的颜色初始为蓝色。他按照以下规则在图上行走，行走过程中可以重复经过节点和边：

1. 如果当前位于节点 $1$，他最喜欢的颜色变为蓝色；否则，如果当前位于节点 $2$，他最喜欢的颜色变为红色。
2. 从当前节点出发，沿一条颜色与他最喜欢的颜色相同的出边移动。可以证明，这样的边一定存在。
3. 他可以选择继续重复以上过程，也可以停止。

按照访问顺序记录节点，得到列表 $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}\ne l_j$。

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

输入格式

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

第二行包含一个长度为 $N$、仅由字符 B 和 W 组成的字符串。第 $i$ 个字符为 B 表示节点 $i$ 为黑色，为 W 表示节点 $i$ 为白色。

保证字符串的第一个字符为 B，第二个字符为 W。

输出格式

输出一行，表示满足条件的列表数量对 $10^9+7$ 取模后的结果。

输入输出样例 #1

输入 #1

4
BWWB

输出 #1

4

说明 #1

四个满足条件的列表为：

• $1\to 2$；
• $1\to 3\to 2$；
• $1\to 3\to 4\to 1\to 2$；
• $1\to 2\to 3\to 1\to 2$。

输入输出样例 #2

输入 #2

12
BWBWBBBWWBBW

输出 #2

3377552

数据范围

• $3\le N\le 50$；
• 输入字符串的第一个字符为 B，第二个字符为 W。

子任务

附加文件