Cosmic Cow Colorings

It is the year $3000$ and Bessie has become the first cow to venture into space! On her interstellar journey, she discovers a number line with $N$ points (numbered from $1$ to $N$, where $2\le N\le 5\cdot10^5$). Initially every point is white.

Bessie can perform any number of operations. In each operation, she chooses a position $i$ on the number line and a positive integer $x$ such that the entire interval $[i, i+2x-1]$ lies within the number line. Then she colors the interval $[i, i+x-1]$ red and the interval $[i+x, i+2x-1]$ blue. Importantly, the chosen interval must be completely uncolored (i.e. none of its points have been painted red or blue yet).

Farmer John gives Bessie a string $s$ of length $N$ consisting of characters R, B and X. For each position $i$:

• If $s_i=R$, then point $i$ must be red.
• If $s_i=B$, then point $i$ must be blue.
• If $s_i=X$, then there is no color restriction on point $i$ (it may remain white if not painted).

Two coloring schemes are considered different if there exists at least one point with a different final color. Compute the number of final coloring schemes that satisfy Farmer John's preferences. Since the answer can be large, output it modulo $10^9+7$.

inputFormat

The input consists of two lines:

1. The first line contains a single integer $N$.
2. The second line contains the string $s$ of length $N$ composed only of the characters R, B and X.

outputFormat

Output a single integer: the number of valid coloring schemes modulo $10^9+7$.

sample

5
RBRXX

1