很久很久以前（7年前），你曾身处东南亚一条东西走向的公路上，这条公路据称至少含有一块金块，你当时带有一个有限但可靠的黄金探测器。在那次淘金经历让你变得极其富有之后，你尝试并厌倦了所有能想到的活动。在你的豪宅中闲逛时，你发现了一些关于那次淘金的笔记。

这些笔记以公路示意图的形式呈现。对于公路的每一公里，你都有以下 5 种标记之一：

• <，表示距离最近的金块在西侧，
• =，表示距离最近的东侧金块和西侧金块距离相等，且该位置没有金块，
• >，表示距离最近的金块在东侧，
• o，表示该位置有一块金块，或者
• .，表示对该位置一无所知。

由于每一个未知的（.）位置可能独立地包含或不包含金块，你需要找出有多少种金块放置方案既符合你所有的笔记，又使得整条公路至少包含一块金块。由于输出可能是一个非常大的数字，我们仅要求你输出结果除以质数 $10^9 + 7$ ($1000000007$) 的余数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 行。每行包含一个字符串 $S$，代表单个测试用例。$S$ 的第 $i$ 个字符表示你笔记中关于从西向东第 $i$ 公里的标记，使用上述代码表示。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是符合你笔记且至少包含一块金块的不同金块放置方案数，对质数 $10^9 + 7$ ($1000000007$) 取模。

数据范围

$1 \le T \le 100$。 $S$ 的每个字符均为 <（小于号）、=（等于号）、>（大于号）、o（小写字母 o）或 .（句点）。 至少存在一个字符不是 .（句点），且并非所有字符都是 .（句点）。

子任务

测试集 1（可见判决） 时间限制：20 秒。 $2 \le |S| \le 100$。

测试集 2（隐藏判决） 时间限制：40 秒。 $2 \le |S| \le 5 \times 10^5$。

样例

样例输入 1

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

样例输出 1

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

说明

在样例 1 中，有三种有效的放置方案，分别对应公路 oo<=>o<、oo<=>oo 和 o<<=>>o。

在样例 2 中，没有有效的放置方案。

在样例 3 中，唯一的有效放置方案对应公路 o=o。注意，有效的放置方案必须始终使得公路至少包含一块金块。

在样例 4 中，所有 $2^{17}$ 种放置方案均有效。在这种情况下，选择将所有未知（.）位置留空（不放置金块）的方案也是有效的，因为在这种方案下，整条公路仍然包含一块金块。