E. Cards in a Row
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

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$$$.

Examples
Input
XXOXO
Output
5
Input
XXXXXX
Output
0
Input
OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output
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$$$.