Coco enjoys playing the chocolate flipping game when bored. This is a single-player game played with coin-shaped chocolates that have two distinct sides, which proceeds as follows:

1. Arrange the chocolates in a row, with each showing either the front or the back.
2. Pick one chocolate showing the front side to eat, and flip an adjacent chocolate (either to the left or to the right). A chocolate that was showing the front side becomes the back side, and vice versa. There can be 2, 1, or 0 adjacent chocolates. If there are 2 neighbors, the two neighbors do not become adjacent to each other after the chocolate is eaten.
3. You win if you eat all the chocolates by repeating step 2. You lose if you cannot perform step 2 while one or more chocolates remain.

Hanbyeol, who watched Coco play this game, posed the following problem. Help Coco solve it:

• Given the initial state of the chocolates, if you can flip any number of chocolates as you wish, how many ways are there to reach a state from which it is possible to win the chocolate flipping game?

Input

The first line contains the number of test cases $T$ $(1 \le T \le 1\,000)$.

For each test case, a string of length $N$ representing the state of the chocolates is given on a single line without spaces $(1 \le N \le 100\,000)$. This string consists only of the characters H, T, and ?, where H represents the front side, T represents the back side, and ? represents a chocolate that can be flipped to either side as desired.

The sum of $N$ over all test cases does not exceed $1\,000\,000$.

Output

For each test case, output the answer to the problem modulo $1\,000\,000\,007$ on a single line.

Examples

Input 1

4
HTT
THT
TTT
TTTT?TTTT

Output 1

1
1
0
1