06749. USACO·星际区间 未做

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

• 选择一个数轴上的位置 $i$ 和一个正整数 $x$。然后，将区间 $[i,i+x-1]$ 中的所有点涂成红色，区间 $[i+x,i+2x-1]$ 中的所有点涂成蓝色。所有选择的区间必须是不交的（即区间 $[i,i+2x-1]$ 中的点不能已经被涂成红色或蓝色）。同时，整个区间必须落在数轴内（即 $1\le i\le i+2x-1\le N$）。

Farmer John 给了 Bessie 一个长度为 $N$ 的字符串 $s$，由字符 'R'，'B' 和 'X' 组成。该字符串表示了 Farmer John 对每个点的颜色偏好：$s_i=\text{’R’}$ 表示第 $i$ 个点必须被涂成红色，$s_i=\text{’B’}$ 表示第 $i$ 个点必须被涂成蓝色，$s_i=\text{’X’}$ 表示第 $i$ 个点的颜色没有限制。

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

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

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

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

【样例解释】

• 测试点 5-6：$N\le 10^4$。

• 测试点 7-13：$s$ 中至多 $100$ 个字符不为 'X'。

• 测试点 14-23：没有额外限制。

【数据规模与约定】

• 测试点 4：$N\le 500$。

• 测试点 5-6：$N\le 10^4$。

• 测试点 7-13：$s$ 中至多 $100$ 个字符不为 'X'。

• 测试点 14-23：没有额外限制。

供题：Chongtian Ma，Alex Liang