Page not loading? Try clicking here.
Placeholder

#10466

Old Gold 20s 2048MB

Problems

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).


Input

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.


Output

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).


Example 

4
o..=>..
...o>..........
.=.
.........o........
Case #1: 3
Case #2: 0
Case #3: 1
Case #4: 131072
In Sample Case #1, there are three valid placements resulting in roads ooo, oooo and o>o. In Sample Case #2, there is no valid placement. In Sample Case #3, the only valid placement results in road o=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.

Source

GCJ 2023d D

You must sign in to write code.