P12964 [GCJ Farewell Round #4] Old Gold

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

**Sample Explanation** In Sample Case #1, there are three valid placements resulting in roads $\mathrm{o} \mathrm{o}\mathrm{o}