Chocolate Flip Game (Bitter)

Coco likes to play the chocolate flip game when he is bored. The chocolate flip game is a one-player game played with coin-shaped chocolates that have different faces on each side. It proceeds as follows.

1. Place the chocolates in a row, each showing either its front or its back side. Call this state the initial state.
2. Pick a chocolate that shows its front side and eat it. Then flip that chocolate and the chocolate adjacent to it on the left or the right. A front side becomes a back side, and a back side becomes a front side. The number of adjacent chocolates can be 2, 1, or 0. When there are 2 adjacent chocolates, after you eat the chocolate, the two become adjacent to each other.
3. Repeat step 2. If you eat all the chocolates, you win. If at least one chocolate remains and step 2 cannot be performed, you lose.

Hanbyeol watched Coco play this game and made the following problem. Help Coco solve it.

• Given an initial state in which some chocolates can be flipped as you wish, how many initial states have a winning method for the chocolate flip game?

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

For each test case, a single line contains a string of length $N$ with no spaces. $(1\le N\le 100\,000)$ The string consists only of the characters H, T, and ?. H means a front side, T means a back side, and ? means a chocolate that can be flipped as you wish.

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

For each test case, print on a line the answer modulo $1\,000\,000\,007$ ($=10^9+7$).