题目描述

很久很久以前（7 年前），你曾在东南亚一条东西向的道路上寻找黄金，这条道路已知至少含有一块金块。当时你使用了一个有限但可靠的金块探测器。在靠这些黄金暴富后，你尝试并厌倦了所有能想到的活动。某天，你在巨大的豪宅中闲逛时，发现了当年寻金时的一些笔记。

这些笔记以道路示意图的形式记录。对于道路的每一公里，笔记上有以下 5 种标记之一：

• $<$，表示最近的金块位于西侧，
• $=$，表示东西两侧最近的金块距离相等，且当前位置没有金块，
• $>$，表示最近的金块位于东侧，
• o，表示当前位置有金块，或
• .，表示该位置信息未知。

由于每个未知位置（.）可以独立地选择是否放置金块，你需要计算在所有 $2^{k}$ 种可能的金块分布中，有多少种分布既符合所有笔记记录，又能保证整条道路上至少存在一块金块。由于结果可能非常大，只需输出结果对质数 $10^{9}+7$（即 $1000000007$）取模后的余数。

输入格式

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 行，每行包含一个字符串 $\mathbf{S}$，表示一个测试用例。字符串 $\mathbf{S}$ 的第 $i$ 个字符表示从西向东第 $i$ 公里处的标记，使用上述代码表示。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是符合笔记记录的金块分布数量，对质数 $10^{9}+7$ 取模后的结果。

输入输出样例 #1

输入 #1

4
o..=>..
...o>..........
.=.
.........o........

输出 #1

Case #1: 3
Case #2: 0
Case #3: 1
Case #4: 131072

说明/提示

样例解释

在样例 #1 中，有三种有效的金块分布，分别对应道路 $\mathrm{o} \mathrm{o}<=>\mathrm{o}<$、$\mathrm{o} \mathrm{o}<=>\mathrm{oo}$ 和 $\mathrm{o}<<=>\mathrm{o}$。

在样例 #2 中，没有有效的金块分布。

在样例 #3 中，唯一有效的分布对应道路 $\mathrm{o}=\mathrm{o}$。注意有效的分布必须保证整条道路上至少有一块金块。

在样例 #4 中，所有 $2^{17}$ 种分布都有效。在这种情况下，即使选择在所有未知位置（.）不放置金块，整条道路仍有一块金块，因此这种分布也是有效的。

限制

• $1 \leq \mathbf{T} \leq 100$。
• 字符串 $\mathbf{S}$ 的每个字符是 $<$（小于）、$=$（等于）、$>$（大于）、o（小写字母 o）或 .（句点）之一。
• $\mathbf{S}$ 中至少有 1 个但并非全部字符是 .（句点）。

测试集 1（5 分，可见评测结果）

• 时间限制：20 秒。
• $2 \leq \mathbf{S}$ 的长度 $\leq 100$。

测试集 2（17 分，隐藏评测结果）

• 时间限制：40 秒。
• $2 \leq \mathbf{S}$ 的长度 $\leq 5 \times 10^{5}$。