题目描述

有 $N$ 个节点，编号为 $1,2,\ldots,N$。每个节点为黑色或白色，其中节点 $1$ 为黑色，节点 $2$ 为白色。

任意两个不同节点之间都有两个方向的有向边。从节点 $i$ 到节点 $j$ 的边颜色按下表确定：

编号关系	两个节点同色	两个节点异色
$i<j$	红色	蓝色
$i>j$	蓝色	红色

从节点 $1$ 开始行走，最初喜欢蓝色。每一步只能沿一条与当前喜欢的颜色相同的有向边行走。每当到达节点 $1$，喜欢的颜色变为蓝色；每当到达节点 $2$，喜欢的颜色变为红色；到达其他节点时，喜欢的颜色不变。

求满足下列要求的有限行走序列数量：

• 起点为节点 $1$，终点为节点 $2$。
• 每个编号大于等于 $3$ 的节点至多出现一次，节点 $1,2$ 可以出现多次。
• 不能立即沿原路返回：若行走序列为 $l_1,l_2,\ldots,l_k$，则对所有 $3\le j\le k$，都有 $l_{j-2}\ne l_j$。

到达节点 $2$ 时，可以结束行走，也可以继续行走并在之后再次到达节点 $2$ 时结束。节点编号序列不同的行走视为不同方案。输出方案数对 $10^9+7$ 取模的结果。

输入格式

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

第二行包含一个长度为 $N$ 的字符串 $C$。若 $C_i$ 为 B，表示节点 $i$ 为黑色；若为 W，表示节点 $i$ 为白色。

输出格式

输出一个整数，表示合法行走序列数量对 $10^9+7$ 取模的结果。

数据范围

对于所有测试数据，$3\le N\le50$，$C$ 仅含字符 B 和 W，且 $C_1=$ B、$C_2=$ W。

子任务

编号	分值	缩减范围	附加限制
1	4	$N \le 8$	—
2	12	$N \le 20$
3	16	—	恰好有一个黑色节点。
4			存在 $2\le i\le N$，使得节点 $2,3,\ldots,i$ 均为白色，其余节点均为黑色。
5	24		黑色节点不超过 $5$ 个。
6	28		—

样例 1

4
BWWB

4

样例 1 说明

四种合法行走为 $1\to2$、$1\to3\to2$、$1\to3\to4\to1\to2$ 和 $1\to2\to3\to1\to2$。

最后一种行走在首次到达节点 $2$ 后继续行走，仍然是一个独立的合法方案。

样例 2

12
BWBWBBBWWBBW

3377552