Old Gold

A long, long time ago ($7$ years) you were on a West-East road in Southeast Asia that is known to contain at least one gold nugget. You had a limited but reliable gold detector. After getting immensely rich from that gold, you tried every activity you could think of and got bored of all of them. While wandering around your huge mansion, you found some notes from that gold hunt.

The notes are a diagram of the road. For each kilometer of road, one of five markings is written:

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

Each of the $k$ unknown (.) positions may or may not contain a gold nugget, independently of the others. Count how many of the $2^k$ placements of gold agree with all the notes and leave at least one gold nugget on the road overall. The count can be very large, so output it modulo the prime $10^9+7$ ($1000000007$).

The first line contains the number of test cases $T$. Each of the next $T$ lines contains a string $S$ that describes one test case. The $i$-th character of $S$ is the marking for the $i$-th kilometer of road, from West to East, using the code above.

For each test case, output one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of valid gold placements modulo $10^9+7$ ($1000000007$).

• $1 \le T \le 100$.
• Each character of $S$ is one of < (less than), = (equals), > (greater than), o (lowercase o), or . (period).
• $S$ has at least 1 character, and not all characters of $S$ are . (period).

In Sample Case #1, there are three valid placements, which result in the roads oo≤>o<, oo≤>oo, and o<≤>>o.

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

In Sample Case #3, the only valid placement results in the road o=o. A valid placement must always leave at least one gold nugget on the road.

In Sample Case #4, all $2^{17}$ placements are valid. The placement that leaves every unknown (.) position empty is also valid, because the road still has one gold nugget in that placement.