Hard Sculptural Project

Time limit2sMemory limit512 MB

Summary
Given a string of 'w' (work, consume 1) and 'o' (rest, gain 1), delete the fewest characters so every prefix has more gains than work and the total balances, then count the ways.
Level

Medium6 of 10

Topics
Dynamic programming, Greedy, Combinatorics, String
Solved
No attempts yet

Problem

The problem statement is almost identical to the previous problem, with a few modified sentences shown in bold.

A sculptor from his youth, da Vinci designed many sculptures, yet few were brought to completion, and only one of them, The Virgin with the Laughing Child, survived. Completing this sculpture took da Vinci a long time and a lot of materials.

Da Vinci planned to spend n days on the first phase of this project. Initially, he had no materials to sculpt. On each day, he would either take a day off (marked 'o') and go to the market to buy 1 unit of materials, or work (marked 'w') on the sculpture and consume 1 unit of materials. After creating the schedule, however, da Vinci noticed it was not realistic: on some workdays he might have no material to work with at all, and in the end he might be left with unused materials. To ensure smooth progress on this sculptural project, da Vinci decided to cancel some of his activities on certain days so that:

  1. Starting with no material, da Vinci would have at least 1 unit of materials to sculpt on each workday.
  2. After n days, da Vinci would end up with no material left.
  3. The number of canceled activities is minimized. (Da Vinci did not want to modify his original schedule too much!)

Da Vinci would like to know the number of ways to cancel the minimum number of activities to satisfy these conditions. Two schedules are considered different if there exists at least one activity canceled in one schedule but preserved in the other.

Input

The first line contains a number 1 ≤ K ≤ 10, which is the number of input data sets in the file. This is followed by K data sets of the following form.

Each data set is described by a single line containing a non-empty string S, describing da Vinci's original schedule. The length of S is at most 1000 and it consists of 'w' and 'o' only. You can compute n by reading the length of S.

Output

For each data set, first output “Data Set x:” on a line by itself, where x is its number.

Then output the number of ways to cancel the minimum number of activities to make the schedule feasible. Since the answer might be very large, you should output the answer modulo 10^9 + 7.

Each data set should be followed by a blank line.

Examples1

  1. Example 1

    Input
    4
oowowwowowwoow
www
owowowowwo
oooooooooowwwww
    Expected output
    Data Set 1:
12

Data Set 2:
1

Data Set 3:
5

Data Set 4:
252