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
1
0
1