Coco在无聊的时候喜欢玩翻巧克力游戏。翻巧克力游戏是一种使用正反面不同的硬币状巧克力进行的单人游戏，游戏规则如下。

1. 将巧克力排成一排，使其正面或反面朝上。
2. 拿走并吃掉一个正面朝上的巧克力，然后将与该巧克力相邻的（左侧和右侧的）所有巧克力翻面。原本是正面的巧克力翻面后变成反面，原本是反面的则变成正面。相邻的巧克力可能有 $2$ 个、$1$ 个或 $0$ 个。如果相邻的巧克力有 $2$ 个，在吃掉该巧克力后，这两个巧克力将变得彼此相邻。
3. 重复步骤 2，如果吃掉了所有的巧克力，则获得胜利。如果还剩有 $1$ 个或更多的巧克力，但无法再执行步骤 2，则失败。

看到Coco玩这个游戏后，Hanbyul提出了以下问题。让我们帮助Coco解决这个问题。

• 在给定的巧克力中，有若干个可以按意愿决定其初始朝向。问有多少种确定这些巧克力初始朝向的方案，使得游戏存在获胜的方法？

输入格式

第一行包含测试数据组数 $T$。$(1 \le T \le 1\,000)$

对于每组测试数据，输入一行一个长度为 $N$ 且不含空格的字符串，表示巧克力的状态。$(1 \le N \le 100\,000)$ 该字符串仅由 H、T、? 三种字符组成，其中 H 表示正面，T 表示反面，? 表示可以按意愿决定初始朝向的巧克力。

所有测试数据的 $N$ 之和不超过 $1\,000\,000$。

输出格式

对于每组测试数据，在一行中输出答案模 $1\,000\,000\,007$ 的余数。

样例

输入样例 1

4
HTT
THT
TTT
TTTT?TTTT

输出样例 1

1
0
0
1