Coco enjoys playing the chocolate flipping game when bored. The chocolate flipping game is a single-player game played with coin-shaped chocolates that have two distinct sides, and it proceeds as follows:
- Arrange the chocolates in a row, with each showing either the front or the back.
- Pick one chocolate showing the front side and eat it, then flip an adjacent chocolate to its left or right. If a chocolate was showing the front, it becomes the back, and if it was showing the back, it becomes the front. The number of adjacent chocolates can be 2, 1, or 0. If there are 2 neighbors, after the chocolate is eaten, the two remaining neighbors become adjacent to each other.
- 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 you can 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, T represents the back, 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 0 0 1