Cards in a Row
Description
You are given $n$ cards $c_1, c_2, ..., c_n$ arranged in a row. Some of the cards are lying face-up, and some of them are face-down. Flipping a face-up card makes it face-down, and vice versa. In one operation, you may select any face-up card $c_i$, and flip it along with all cards to the right of it. In other words, you may select any card $c_i$ that is face up, and flip all cards $c_j$ such that $j \geq i$.
It can be shown that the maximum number of operations you can possibly perform until it becomes impossible to do so is finite. Please find and output this number.
Since this number might be large, please output it modulo $10^9 + 7$.
The first and only line of input consists of a single string $c_1c_2...c_n$ $(1 \leq n \leq 2 \cdot 10^5)$. If $c_i$ is O, the $i$th card is face-up. Otherwise, $c_i$ will be X, representing a face-down card.
On the first and only line, output the answer to the problem, modulo $10^9 + 7$.
Input
The first and only line of input consists of a single string $c_1c_2...c_n$ $(1 \leq n \leq 2 \cdot 10^5)$. If $c_i$ is O, the $i$th card is face-up. Otherwise, $c_i$ will be X, representing a face-down card.
Output
On the first and only line, output the answer to the problem, modulo $10^9 + 7$.
XXOXO
XXXXXX
OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
5
0
294967268
Note
In the first sample test case, one maximum-length sequence of operations is:
$$\tt{XXOXO} \rightarrow \tt{XXOX\color{red}{X}} \rightarrow \tt{XX\color{red}{XOO}} \rightarrow \tt{XXXO\color{red}{X}} \rightarrow \tt{XXX\color{red}{XO}} \rightarrow \tt{XXXX\color{red}{X}}$$
The red characters represent which cards have been flipped.
In the second sample, no operations are possible to perform on the initial sequence of cards, so the answer is $0$.