BearCries | Topcoder Archive

Problem Statement

Limak is a polar bear who often chats online with his friends. Nowadays, bears often use emoticons to express their feelings. In this problem we consider one particular emoticon: the crying emoticon.

A crying emoticon consists of an arbitrary positive number of underscores between two semicolons. Hence, the shortest possible crying emoticon is ";_;" (quotes for clarity). The strings ";__;" and ";_____________;" are also valid crying emoticons.

Today Limak is sad, so he sent his friend a sequence of crying emoticons. However, due to a network malfunction all those emoticons got mixed together into a single string.

You are given a String message containing the message Limak's friend received. You guess that the message can be divided into one or more crying emoticons. Each emoticon must be a subsequence of the message, and each character of the message must belong to exactly one emoticon. Note that the subsequences are not required to be contiguous.

Let X be the number of ways in which one can divide the given message into emoticons. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:: BearCries
Method:: count
Parameters:: String
Returns:: int
Method signature:: int count(String message)
(be sure your method is public)

Constraints

message will contain between 1 and 200 characters, inclusive.
Each character in message will be either semicolon or underscore.

Examples

```
";_;;_____;"
```
```
Returns: 2
```
There are two ways to divide this string into two crying emoticons. One looks as follows: ;_; ;_____; and the other looks like this: ;_ ; ; _____;
```
";;;___;;;"
```
```
Returns: 36
```
This message consists of 3 semicolons, 3 underscores and 3 semicolons again. Clearly, we have to divide this message into exactly three crying emoticons, each with a single underscore. There are 36 different ways to do so.
```
"_;__;"
```
```
Returns: 0
```
As this message begins with an underscore, it clearly cannot be divided into one or more crying emoticons: each crying emoticon starts with a semicolon.

";_____________________________________;"

Returns: 1

```
";__;____;"
```
```
Returns: 0
```
```
";_;;__;_;;"
```
```
Returns: 52
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.