题目描述

现在是公元 $3000$ 年，Bessie 成为了第一头进入太空的奶牛！在她穿越星际的旅程中，她发现了一条有 $N$（$2 \leq N \leq 5 \cdot 10^5$）个点的数轴，点的编号从 $1$ 到 $N$。所有点初始时都是白色的。她可以执行任意次以下操作。

选择一个数轴上的位置 $i$ 和一个正整数 $x$。然后，将区间 $[i, i + x - 1]$ 中的所有点涂成红色，区间 $[i + x, i + 2x - 1]$ 中的所有点涂成蓝色。所有选择的区间必须是不交的（即区间 $[i, i + 2x - 1]$ 中的点不能已经被涂成红色或蓝色）。同时，整个区间必须落在数轴内（即 $1 \leq i \leq i + 2x - 1 \leq N$）。 Farmer John 给了 Bessie 一个长度为 $N$ 的字符串 $s$，由字符 $\tt R$，$\tt B$ 和 $\tt X$ 组成。该字符串表示了 Farmer John 对每个点的颜色偏好：$s_i=\texttt{R}$ 表示第 $i$ 个点必须被涂成红色，$s_i = \texttt{B}$ 表示第 $i$ 个点必须被涂成蓝色，$s_i = \texttt{X}$ 表示第 $i$ 个点的颜色没有限制。

帮助 Bessie 计算满足 Farmer John 偏好的不同的数轴涂色方案的数量。两个涂色方案是不同的，如果至少一个对应点的颜色不同。由于答案可能很大，输出答案模 $10^9+7$ 的余数。

输入格式

输入的第一行包含一个整数 $N$。

下一行包含字符串 $s$。

输出格式

输出满足 Farmer John 偏好的不同的数轴涂色方案的数量，对 $10^9+7$ 取模。

6
RXXXXB

5

6
XXRBXX

6

12
XBXXXXRXRBXX

18

提示

样例 1 解释：

Bessie 可以选择 $i=1,x=1$（即将点 $1$ 涂成红色，点 $2$ 涂成蓝色）以及 $i=3,x=2$（即将点 $3,4$ 涂成红色，点 $5,6$ 涂成蓝色）来得到涂色方案 $\tt RBRRBB$。

其他涂色方案有 $\tt{RRBBRB}$，$\tt{RBWWRB}$，$\tt{RRRBBB}$ 和 $\tt{RBRBRB}$。

样例 2 解释：

六种涂色方案为 $\tt{WWRBWW}$，$\tt{WWRBRB}$，$\tt{WRRBBW}$，$\tt{RBRBWW}$，$\tt{RBRBRB}$ 和 $\tt{RRRBBB}$。

• 测试点 $4$：$N\leq 500$。
• 测试点 $5\sim 6$：$N\leq 10^4$。
• 测试点 $7\sim 13$：$s$ 中至多 $100$ 个字符不为 $\tt{X}$。
• 测试点 $14\sim 23$：没有额外限制。