有一个包含 $N$ 个节点的图，节点编号从 $1$ 到 $N$。每个节点被染成黑色或白色。此外，已知节点 $1$ 为黑色，节点 $2$ 为白色。对于任意 $i$ 和 $j$（$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$。

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

注意，“mod”在大多数编程语言中对应 % 运算符，表示除法后的余数。例如，$5 \pmod 3 = 2$ 且 $17 \pmod 4 = 1$。

输入格式

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

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

子任务

下表显示了 25 分的分布情况：

输出格式

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

样例

样例输入 1

4
BWWB

样例输出 1

4

说明

该图如下所示：

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

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

在下划线标注的节点处，最喜欢的颜色为红色，其余情况为蓝色。

样例输入 2

12
BWBWBBBWWBBW

样例输出 2

3377552