Statistics

Problem Statement for "BearCries"

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

  1. ";_;;_____;"

    Returns: 2

    There are two ways to divide this string into two crying emoticons. One looks as follows: ;_; ;_____; and the other looks like this: ;_ ; ; _____;

  2. ";;;___;;;"

    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.

  3. "_;__;"

    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.

  4. ";_____________________________________;"

    Returns: 1

  5. ";__;____;"

    Returns: 0

  6. ";_;;__;_;;"

    Returns: 52

  7. "_"

    Returns: 0

    fake

  8. "_"

    Returns: 0

    fake

  9. ";"

    Returns: 0

  10. "_"

    Returns: 0

  11. ";;"

    Returns: 0

  12. "__"

    Returns: 0

  13. "_;"

    Returns: 0

  14. ";_"

    Returns: 0

  15. "_;_"

    Returns: 0

  16. ";_;"

    Returns: 1

  17. ";__;"

    Returns: 1

  18. ";_;_"

    Returns: 0

  19. ";_;;"

    Returns: 0

  20. ";;_;;"

    Returns: 0

  21. ";;_;__;_;;"

    Returns: 100

  22. ";;;__;__;__;___;_;;;"

    Returns: 46273500

  23. ";_;;__;__;_________;;_;;__;;_;"

    Returns: 249069926

  24. ";;;_;;;;;;_;;;;;;;_;;_;;;_;_;___;_;___;;;__;_;___;;;_;;__;;_;;;;_;;;___;;_;;;;;;"

    Returns: 389715415

  25. ";;;_;;;;;;;_;;_;;__;_;;_;_;;;____;;__;;_______;_____;___;;____;_;________________;____;__;______;;___;__;;___;;_;;;_______;;;;____;;__;;;_;;_;_;_;;;;;"

    Returns: 629166273

  26. ";;;;;;;;;_;_;;;;;;;__;;;;;;;;__;__;_;;__;;;;_;;_;;;_;;__;;;;__;___;;;;;;;;;__;;;__;___;__;__;;___;_;;_;__;;;;;;;____;____;;;;;;;;;;;__;___;;;;;;;;;;;;;;;____;_;_;;_;;;_;_;_;;;_;;;;;_;_;_;;;_;;;;;_;;;;"

    Returns: 707494658

  27. ";;;_;;;;;;;_;__;;;;_;;;;;;;;;;_;_;;___;;;;_;;_;____;_;;;;;;;__;__;;_;__;;;;;;___;;;_;;;;;__;_;;;_;;;_;_;;;_;;_;_;;;;___;;;______;;__;;;;;;_;;_;;;;_;;;;_;;;;;_____;;;;;;_;;;;;_____;;_;;;;;;__;;;;;;__;;"

    Returns: 936117765

  28. ";;;__;_;;;;;;__;;_;;_;;_;;;__;;;;;;;;;;;;_;_;;;_;__;;;_;__;;;;;;;__;;;_;__;;;;;_;;_;;__;_;;;_;;;_;;_;;;______;;_;__;_;;_;;;;;___;_;;;____;;____;;;;;;_;__;_;__;__;;;;_;;;;;;___;;__;;;;;;;;;;;;;;;;;;;;;"

    Returns: 136316705

  29. ";;_;_;;;;;;;;_;_;_;;;;;__;__;;;;_;;;__;;_;;;;_;_;___;___;_;_____;____;;;_;_;;_;;_;___;______;______;_;__________;;_;_;_;___;__;;____;_;__;;;;___;_;_____;;;_;;;;_;_;;;_;;_;__;_;;;_;_;__;;;;__;;;;;;_;;;"

    Returns: 215639354

  30. ";;;;;;_;;_;_;_;;;_;;;;___;_;;;__;;__;_;_;;;;__;__;;____;_;__;;;;_____;_;;;_;_;__;_;___;_;____;__;____;;;_____;;___;;_________;_;_;_____;;;_;;_;;__;;;;;__;__;____;;;__;;;;_;_;;;___;_;_;;;;;_;;;;;;_;;;;"

    Returns: 700113804

  31. ";;;;;;;;;;;_;_;;____;;;;;;;_;_;;;_;__;;___;;_;__;_;_;___;____;_;;;_;_;___;___;_;;_______;;_;__;____;_;__;_______;;_____;_____;_;__;___;;;___;___;;;__;_;_;;;___;;;;;_;____;_;;;;;_;;__;;;;;;;;_;;;;_;;;;"

    Returns: 58971798

  32. ";;;;___;;;_;_;;;;;;;_;;_;_;;_;;;________;_;_;;_____;;_;_;_;____;__;;_______;_______;__;;_______;____________;_________________;;__;___;___;____;_;__;_;;_;;;____;_;;;;_;_;_;__;__;;;_;;;__;;__;;;;;;;;;;"

    Returns: 0

  33. ";;;;;;;;;;;;__;;;;_;;;;__;;__;;;__;_;_;;_;;___;_;__;;_;__;;____;______________;_;_________;______________;_______;____;__;______;_;;___;;__;__;;;_;____;_______;;_;_;;_;__;;;__;;;;___;_;__;;;;__;;_;;;;"

    Returns: 24955813

  34. ";;;_;;;_;;_;;_;;;__;;_;;_;;_;;__;_;___;__;_;_;;______;;___;_____________;__;___________________________;____;__;____;____;;______________;_;____;____;__;__;_;;__;;_;_;_;_;_;_;_;;____;_____;;;;;;_;;_;;"

    Returns: 646986609

  35. ";;_;;_;_;;_;;;;;____;__;_;;;;_;;___;;_;;____;;__;_____;;_;_____;___;_____;_________;_________;______;________________;__;;____;_______________;_;_;______;_;;;_;___;__;_;;_;;;_;___;;;;__;;;__;;__;_;;;;"

    Returns: 238258736

  36. ";;;;;;;__;;__;;_;;__;_;;___;_;;;_;_;__;__;______________;;_;__;____;;________________________;__;__________________;_____________;_____;;_________________;__;_;__;_;___;_;_;__;_;____;;;_;;;_;_;__;;;;;"

    Returns: 0

  37. ";;;;_;;;;__;____;;_;;_;;____;;;_;_;_;;____;_;;________;__;_;________________;__________;_________________________;__________________;_____;__;;_;;_;__________;_;__;__;_;_;;___;;;;___;;____;;;_;;_;;_;;"

    Returns: 365605098

  38. ";_;;;_;;;_;;_;_;_;;_;;_;_____;__;_____;;;;______;__;_____;________;___________;__________________________________________;__________;______;___;___;____;__________;;;;;________;__;_;;;;__;;;_;_;;;_;;;"

    Returns: 755723250

  39. ";;_;;;___;;_;_;;_;;__;__;__;;__;____;;;___;;____;;_____;_____;_____;_____________________________;_______________________;____________________;___________;______;;;;;___;;;_;______;_;_;;;_;;;;;_;_;;_;"

    Returns: 792286190

  40. ";;;;;;__;_;;__;_________;;;_;___;;_;_;_________;______;;________;_________________________________________________________;_________;_________________;___;_;__;__;;____;______;__;_;__;__;;____;_;;;;_;"

    Returns: 0

  41. ";_;;_;;_____;;;;_;_;___;____;;___;_______;_;_;______;____;___;__________________________________________________________;__________________________;___;___;__;____;___;__;___;__;_;_____;;_;__;;;;;;;;;"

    Returns: 483736423

  42. ";_;_;;;;_;_;_;_;__;;__;___;__;___________;;_______________;__________________;____________________________________________;______________;______________________;__;_____;__;__;__;_____;;_;_;__;_;;;_;;"

    Returns: 0

  43. ";;_;;__;;;;_;;__;_;__;____;_;______;______;____;__________________________________________________________________________________________;______;_____________;____;______;_;___;_;_;;_;__;_____;_;;;;;"

    Returns: 754878292

  44. ";_;;_;___;_;;;____;____;_________;__________________________________________________________________________________________________________________;;______________________________;_;________;;;;_;_;;"

    Returns: 640289032

  45. ";;___;;;;_;___;__;_____________;______;_____________________________________________________________________________________________________;____________________________;;______________;_;____;;;__;;;"

    Returns: 87271581

  46. ";;;_;;;;__;;___;___________________;________________________________________________________________________________________________________________________________________;___;____;_____;_;_;_;_;;;_;"

    Returns: 585033062

  47. ";;__;_;____;______;_______________________;______________________________________________________________________________________________________________________________________;_;;_______________;;;;"

    Returns: 336597025

  48. ";;_;_;_________;____;____________________________________________________;____________________________________________________________________________________;___________________________;____;;___;_;;"

    Returns: 319434346

  49. ";;_;;___;________;___;______________________________________________________________________________________________________________________________________________________;_______;_______;_____;__;;;"

    Returns: 244067381

  50. ";_;__;;_______________________________________________________________________________________________________________________________________________________________________________;__________;____;;"

    Returns: 443995578

  51. ";_;______;_______;_;_______________________________________________________________________________________________________________________________________________________________________________;;_;;"

    Returns: 0

  52. ";_;____;_____;___________________________________________________________________________________________________________________________________________________________________;__________;________;_;"

    Returns: 179158160

  53. ";__;___________;____________________________________________________________________________________________________________________________________________________________________________________;_;;"

    Returns: 508291236

  54. ";;____________________;____________________________________________________________________________________________________________________________;_________________________________________________;_;"

    Returns: 141246040

  55. ";;;________________________________________________________________________________________________________________________________________________________________________________________;__________;;"

    Returns: 676779488

  56. ";_;________________________________________________________________________________________________________________________________________________________________________________;___________________;"

    Returns: 581415239

  57. ";__;_______________________________________________________________________________________________________________________________________________________________________________________________;___;"

    Returns: 814450962

  58. ";___;______________________________________________________________________________________________________________________________________________________________________________________________;___;"

    Returns: 907225484

  59. ";______________________________________________________________________________________________________________________________________________________________________________________________________;"

    Returns: 1

  60. ";;____________________________________________________________________________________________________________________________________________________________________________________________________;;"

    Returns: 62430630

  61. ";;;;;;;;;;;;;;;__________________________________________________________________________________________________________________________________________________________________________;;;;;;;;;;;;;;;"

    Returns: 50044732

  62. ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;____________________________________________________________________;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;"

    Returns: 300917874

  63. ";__;____;;__;;;_;;_;;;;;;;;;____;;;;________;;;;_______________________________;;;;;;;;____;;;;;;;;;_;;__;_;;"

    Returns: 561148431

  64. ";___;;___;;___;;___;;___;;___;;___;;___;"

    Returns: 271652359

  65. ";;;;;;;;;;;;;;;;;;;;________________________________________________________________________________________________________________________________________________;;;;;;;;;;;;;;;;;;;;"

    Returns: 376861809

  66. ";_;;_____________________;;___;_________________;_;_____;________;___;__;_____;;___;_______;__;____;__________;___;;_;_____;_;;___;____;__;__;___;__;;;____;_____;;________;_______________;___;_______;"

    Returns: 411252920

  67. ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;__________________________________________________________________;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;"

    Returns: 976309562

  68. ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;____________________________________________________________________________________________________;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;"

    Returns: 843981124

  69. ";________;______;____;____;______________;;_____________________________________;;_____________________________________;"

    Returns: 142174880

  70. ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;______________________________________________________________________;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;"

    Returns: 966319858

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.
This problem was used for: