#P12964. [GCJ Farewell Round #4] Old Gold

    ID: 12766 Type: RemoteJudge 20000~40000ms 2048MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>动态规划 DP2023Google Code Jam

[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 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 kk unknown (.) positions could contain or not contain a gold nugget independently, you want to find out how many of the 2k2^{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 109+710^{9}+7 (10000000071000000007).

输入格式

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

输出格式

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

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 oo<=>o<\mathrm{o} \mathrm{o}<=>\mathrm{o}<, oo<=>oo\mathrm{o} \mathrm{o}<=>\mathrm{oo} and o<<=>o\mathrm{o}<<=>\mathrm{o}.

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

In Sample Case #3, the only valid placement results in road o=o\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 2172^{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

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

Test Set 1 (5 Pts, Visible Verdict)

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

Test Set 2 (17 Pts, Hidden Verdict)

  • Time limit: 40 seconds.
  • 22 \leq the length of S5×105\mathbf{S} \leq 5 \times 10^{5}.