Задача . Interstellar Intervals

Сейчас \(3000\)-ый год,и Беси - первая корова в космосе. Во время своего путешествия между звёздами, она обнаружила числовую прямую с \(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\)).

Фермер Джон даёт Беси строку \(s\) длины \(N\), состоящую из символов \(R\), \(B\), \(X\). Строка представляет предпочитаемую ФД раскраску для каждой точки: \(s_i=R\) означает, что \(i\)-ая точка должна быть выкрашена в красный цвет, \(s_i = B\) означает, что \(i\)-ая точка должна быть выкрашена в синий цвет, а \(s_i = X\) означает, что нет ограничений на цвет \(i\)-ой точки.

Помогите Беси посчитать количество различных способов раскрасить числовую прямую выполнив ограничения ФД. Два способа раскрашивания считаются различными, если хотя бы в одной соответствующей точке они имеют различный цвет. Поскольку это число может быть очень большое, выведите его по модулю \(10^9+7\).

5