코코는 심심할 때면 초콜릿 뒤집기 게임을 즐겨 한다. 초콜릿 뒤집기 게임은 앞뒤가 서로 다른 동전 모양의 초콜릿을 가지고 하는 $1$인용 게임으로, 다음과 같이 진행된다.

1. 초콜릿을 앞면이나 뒷면이 보이도록 일렬로 늘어놓는다.
2. 앞면이 보이는 초콜릿을 하나 집어 먹고, 그 초콜릿과 왼쪽이나 오른쪽으로 이웃한 초콜릿을 뒤집는다. 앞면이었던 초콜릿을 뒤집으면 뒷면이 되고, 뒷면이었다면 앞면이 된다. 이웃한 초콜릿은 $2$개, $1$개, $0$개일 수 있다. 이웃이 $2$개일 경우, 초콜릿을 집어 먹은 후에도 그 둘은 서로 이웃하지 않는다.
3. 2번 과정을 반복하여 초콜릿을 모두 먹으면 승리한다. $1$개 이상의 초콜릿이 남아있는 상태에서 2번 과정을 수행할 수 없으면 패배한다.

코코가 이 게임을 하는 것을 본 한별이는 아래와 같은 문제를 냈다. 코코를 도와 이 문제를 해결해 주자.

• 주어진 초콜릿 중에서 몇 개를 원하는 대로 뒤집을 수 있을 때, 초콜릿 뒤집기 게임에서 승리하는 방법이 있는 경우의 수는 몇 가지일까?

Input

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 1\,000)$

각 테스트 케이스에 대해, 초콜릿의 상태를 나타내는 길이 $N$의 문자열이 공백 없이 한 줄에 주어진다. $(1 \le N \le 100\,000)$ 이 문자열은 H, T, ?의 $3$가지 문자로만 이루어져 있으며, H는 앞면, T는 뒷면, ?는 원하는 대로 뒤집을 수 있는 초콜릿을 뜻한다.

모든 테스트 케이스의 $N$의 합은 $1\,000\,000$을 초과하지 않는다.

Output

각 테스트 케이스에 대해, 문제의 정답을 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.

Examples

Input 1

4
HTT
THT
TTT
TTTT?TTTT

Output 1

1
1
0
1