Page not loading? Try clicking here.
Placeholder

#8186
Subtask

Interstellar Intervals 1s 1024MB

Problems

It's the year 3000, and Bessie became the first cow in space! During her journey between the stars, she found a number line with N (2≤N≤5⋅10^5) points, numbered from 1 to N. All points are initially colored white. She can perform the following operation any number of times.

Choose a position i within the number line and a positive integer x. Then, color all the points in the interval [i,i+x−1] red and all points in [i+x,i+2x−1] blue. All chosen intervals must be disjoint (i.e. no points in [i,i+2x−1] can be already colored red or blue). The entire interval must also fall within the number line (i.e. 1≤i≤i+2x−1≤N).

Farmer John gives Bessie a string s of length N consisting of characters R, B, and X. The string represents Farmer John's color preferences for each point: s_i=R means the i'th point must be colored red, s_i=B means the i'th point must be colored blue, and s_i=X means there is no constraint on the color for the i'th point.

Help Bessie count the number of distinct ways for the number line to be colored while satisfying Farmer John's preferences. Two colorings are different if there is at least one corresponding point with a different color. Because the answer may be large, output it modulo 10^9+7.


Input

The first line contains an integer N.

The following line contains string s.


Output

Output the number of distinct ways for the number line to be colored while satisfying Farmer John's preferences modulo 10^9+7.


Subtask

# Score Condition
#110

N \le 500

#220

N \le 10^4

#330

All but at most 100 characters in s are X.

#440

No additional constraints


Example #1

6
RXXXXB
5

Bessie can choose i=1,x=1 (i.e. color point 1 red and point 2 blue) and i=3,x=2 (i.e. color points 3,4 red and points 5,6 blue) to produce the coloring RBRRBB.

The other colorings are RRBBRB, RBWWRB, RRRBBB, and RBRBRB.


Example #2

6
XXRBXX
6

The six colorings are WWRBWW, WWRBRB, WRRBBW, RBRBWW, RBRBRB, and RRRBBB.


Example #3

12
XBXXXXRXRBXX
18

Source

USACO 2024 December Gold

You must sign in to write code.