题目描述

A long, long time ago (7 years) you were in a West-East road in southeast Asia known to contain at least one gold nugget, with a limited but reliable gold detector. After getting immensely rich with that gold, you have tried and got bored of every conceivable activity. While wandering around your huge mansion you found some notes from that gold hunt.

The notes are in the form of a diagram of the road. For each kilometer of road, you have one of 5 markings:

• $<$, indicating that the closest gold nugget is to the West,
• $=$, indicating that the closest gold nuggets to the East and to the West are at the same distance, and no gold nugget is at that position,
• $>$, indicating that the closest gold nugget is to the East,
• o, indicating that there is a gold nugget at that position, or
• ., indicating that nothing is known about that location.

Since each of the $k$ unknown (.) positions could contain or not contain a gold nugget independently, you want to find out how many of the $2^{k}$ placements of gold are compatible with all your notes and result in the road overall containing at least one gold nugget. Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime $10^{9}+7$ ($1000000007$).

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ lines follow. Each line contains a string $\mathbf{S}$ representing a single test case. The $i$-th character of $\mathbf{S}$ represents the marking in your notes for the $i$-th kilometer of road, from West to East, using the code explained above.

输出格式

For each test case, output one line containing case #$x$: $y$, where $x$ is the test case number (starting from 1) and $y$ is the number of different gold placements that are compatible with your notes, modulo the prime $10^{9}+7$ ($1000000007$).

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

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

提示

Sample Explanation In Sample Case #1, there are three valid placements resulting in roads $\mathrm{o} \mathrm{o}<=>\mathrm{o}<$, $\mathrm{o} \mathrm{o}<=>\mathrm{oo}$ and $\mathrm{o}<<=>\mathrm{o}$.

In Sample Case #2, there is no valid placement.

In Sample Case #3, the only valid placement results in road $\mathrm{o}=\mathrm{o}$. Note that a valid placement must always result in a road containing at least one gold nugget.

In Sample Case #4, all $2^{17}$ placements are valid. In this case, a placement selecting to leave all the unknown (.) positions empty (without a gold nugget) is valid because the road overall still has one gold nugget in such a placement.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• Each character of $\mathbf{S}$ is either $<$ (less than), $=$ (equals), $>$ (greater than), o (lowercase o), or . (period).
• At least 1 and not all characters of $\mathbf{S}$ are . (period).

Test Set 1 (5 Pts, Visible Verdict)

• Time limit: 20 seconds.
• $2 \leq$ the length of $\mathbf{S} \leq 100$.

Test Set 2 (17 Pts, Hidden Verdict)

• Time limit: 40 seconds.
• $2 \leq$ the length of $\mathbf{S} \leq 5 \times 10^{5}$.