Problem 2. Interstellar Intervals

USACO 2024 December Contest, Gold

现在是公元 $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$，由字符 'R'，'B' 和 '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

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

其他涂色方案有 "RRBBRB"，"RBWWRB"，"RRRBBB" 和 "RBRBRB"。

输入样例：

6
XXRBXX

输出样例：

6

六种涂色方案为 "WWRBWW"，"WWRBRB"，"WRRBBW"，"RBRBWW"，"RBRBRB" 和 "RRRBBB"。

输入样例：

12
XBXXXXRXRBXX

输出样例：

18

测试点性质： 测试点 4：$N\le 500$。测试点 5-6：$N\le 10^4$。测试点 7-13：$s$ 中至多 $100$ 个字符不为 'X'。测试点 14-23：没有额外限制。

供题：Chongtian Ma，Alex Liang