31463번 - 초콜릿 뒤집기 게임 (Sweet)

문제

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

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

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

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

입력

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

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

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

출력

각 테스트 케이스에 대해, 문제의 정답을 1ドル,円 000,円 000,円 007$($=10^9+7$)로 나눈 나머지를 한 줄에 출력한다.

제한

힌트