Statistics

Problem Statement for "StepHopJumpMedium"

Problem Statement

You are traversing a dangerous section of a video game level. The section contains some solid terrain blocks (denoted '-') and some blocks with spiky traps (denoted '*'). If you step onto a trap, you die.

You are given the layout of the level in the String level. You are currently standing on the leftmost block of the level. This block is represented by the character level[0] and it is guaranteed to be a solid block.

Your task is to reach the block at the opposite end of the level. This block is also guaranteed to be solid.

You can move in three ways:

  • Take a step (denoted 'S'): move one block to the right.
  • Make a hop (denoted 'H'): hop over one block and land two block to the right of your current block.
  • Make a jump (denoted 'J'): jump over two consecutive blocks and land three blocks to the right of your current position.

For example, if the level is "----", you can traverse it by making three steps (denoted "SSS"), a hop followed by a step ("SH"), a step followed by a hop ("HS"), or a single jump ("J").

If the level is "-**-", the only way to traverse it is by making a jump - remember that you cannot step onto the spiky traps.


In the above way, we can describe any way of traversing the level as a string in which each character is 'S', 'H', or 'J'. Two ways of traversing a level are considered different if they are described by different strings. For example, there are four ways to traverse the level "----", one way to traverse the level "-**-**-", and no ways at all to traverse the level "-*-****-*-".

Let W be the number of different ways in which we can traverse the level described by the String level. Calculate and return the value (W modulo 1,000,000,007).

Definition

Class:
StepHopJumpMedium
Method:
countWays
Parameters:
String
Returns:
int
Method signature:
int countWays(String level)
(be sure your method is public)

Constraints

  • level will contain between 2 and 200 characters, inclusive.
  • Each character of level will be either '-' or '*'.
  • The first and the last character of level will be '-'.

Examples

  1. "----"

    Returns: 4

    The first example from the problem statement.

  2. "-**-"

    Returns: 1

    The second example from the problem statement.

  3. "-*-****-*-"

    Returns: 0

    The third example from the problem statement: there are no solutions.

  4. "------------------------------------"

    Returns: 132436845

    This level consists of 36 dashes. It can be traversed in many different ways. One of them is taking 35 steps, another is taking 11 jumps and then a hop. There are exactly 1,132,436,852 different ways in total. Remember that you should return this value modulo 10^9 + 7.

  5. "--"

    Returns: 1

  6. "-*-"

    Returns: 1

  7. "--*-"

    Returns: 2

  8. "-*--"

    Returns: 2

  9. "--*-**-*-**-*-*-**-*-*-**--*-**----*-*-**-**--*-**-*---**-**-*-*---**-*-**-**-*-**-*-**-**---**--"

    Returns: 864

  10. "--*--*-**-*-**--"

    Returns: 5

  11. "-*--**--**-*--*-**--*-**-*-**-*--**-*-*-**-**--*-*-**-*-*-**-**--**--**--*-*-*-**-**--*---**-**---*-**-**-**-*-*-*--**-*-**-**-**-**-*-**-**-*--"

    Returns: 5760

  12. "-**---*-*--"

    Returns: 6

  13. "---*-----**-**-*-**-*--*-*--**--*--*--*----**-**-*--*-**-*-**-**--**----**-*-**--**--**--*----*--**-*--**-**-**--**-**-*-**-**--**-*-*-**---*-*-*-*-**-*-**---**--*-**-*--*-**-**--*--"

    Returns: 766713600

  14. "-*-**---*-*--*--**--**-*-*-*-**-**-**-**-**--**--**-*--*-**-*-*--**--**-**-**-**-*-**-**-*-**-*-*-**--**-**---**-*-*-*-**-*---**-**-*-*--*-**--*-**-*-*--*--*-**-*-*-*-*-**---**-*---*-*--"

    Returns: 518400

  15. "-*-**-*-*--*---*-*-*-*--**-**-**-*-*-**--**-**-*-**-**-**-**-**-**-*-**-**--**-**-*---**--**--*-*---*--**-*--**--**--**-*--*-*-**-*-**-*--"

    Returns: 14976

  16. "-**-*---*-*-**--**--**-*-*-*-**--*--"

    Returns: 15

  17. "-**-*-*-**--*-*---**-*-*-**-**--*-*--*--*-**--**--**-**--**-*-**-*-**-**--**--*-**--*-**--*-**-*--**-*-**--**-**-*--*---**------**--**-----"

    Returns: 1118208

  18. "-**-*-*--*-*-**-**--**-*--**-*----**--"

    Returns: 36

  19. "-*--*-**-**-*-**-**-**-**-*-**-**-*-**--"

    Returns: 3

  20. "-*-**-*-**-*---*--**-*--*-**---*-*-**--*--**-*-*-**-**-*-**-**----**--**-*-*--**--*---**-**-*--**-**-**--*-*--**--*--"

    Returns: 207360

  21. "---*-**--**-*-**-**-*-*--*-*-*-*-*--**-**-**-**-*--*-*---*--*-*-**--*-**-**-**-*-*---*-*-----*-*---"

    Returns: 358020

  22. "---**-**--*-**--**-*-*--*-*--**-**-**-*-*-**-*----*--**--**-**---**-**--*-*---*--"

    Returns: 11520

  23. "-**-*-**-*---*-**-**-*--**-*-*-*-**-**-*-**--*-*-*--**-*-*--*---**-**-**---**----*-*-*-**-*-**-**---**-**-**-*-**-**-*-*-**-**----**--**-**------**--**-*-**-**-*-**-**-*-**-**--"

    Returns: 399360

  24. "--**-**-**--"

    Returns: 1

  25. "-**-----*-**-*-**-*-*-**-*-*-*-**---*-*-*-**-*-*-*-**-*-*-*-*--**-**-*--*-*--**--**--*-**-*-**-**-**---*-*--**--*-*-**-*--*-*-*-*-**---**--**--*-**--*-**-**-*--**-*---"

    Returns: 1368576

  26. "--**--**-**-**-*-**-**-**--**---*-*--*-**--"

    Returns: 9

  27. "---*-**-**--*-*-**-**--*---**-**-**-**-**--*-**-*--*-**-*--*-*-**-**--*-*-**-**-**-**-*-**--**--*-*-*---**--*-*-*--*---*-**-**---**-*-*--*-**--**-**---*-*--*----**-**-**--**--**-*-*-*-*---**--"

    Returns: 145566720

  28. "-*---**--**-**-*-**-**-*---*-*-**-**-**-*-*-**---*-*-**--**-**-*-*-*-*-**--**-**-**--"

    Returns: 45

  29. "-*-**-**--**------**-**-**-**-*-**-**-*--*-**-**-**-**-*-**--**-*-*---**-**-*---*-*-**-*-*-**--**-**-*-**-*-*-*-**--**-*--*-**-*-*-*-*----*--*---**-**-*--*--**-*-*-**-*--"

    Returns: 1105650

  30. "--*-*---**--**-*-*----*-**-*-**-**--**--**-*-**-*-**----*-**-*--**-**-*-**-**-*-*-*-*-**---*-----**-**-**-*-**-**--*-**-**-**-**-**--*-**---"

    Returns: 150336

  31. "-**--*-*--**-----**--**-**-**-**-**--*--*---*-*--*--**-*-**-**----**-**--"

    Returns: 11760

  32. "-**-*-*-**-**-*--*--**--*--*-**-*--*--*-**--*-**----**---*-**-*-**--"

    Returns: 4800

  33. "-**-*-**--*---**-*-*--*-*---**-*-*-*-*-**-**--*--**--**-**-*-**-**-*--*-*-**-**--"

    Returns: 405

  34. "-**-**-*-**-*-**--*-*-*-*--*-*---**-*----*-**--*-*-**-*-**--*--"

    Returns: 972

  35. "-**----**-*-*--**-*-*--"

    Returns: 16

  36. "-**-*---*-*--**--**-*--*-*-**-**-**--**-*---*--*-*--*-**-*--*-**-----*-**---"

    Returns: 77220

  37. "-*---**-**-----*-*-*-**-*--*-*-*---*-*-**--**-**-**---**-*-**-**-**---**---**-*--**-*---*-*--*--*-**-**---*-*--*--*-**-**---"

    Returns: 15206400

  38. "--*--**---*-**--**-*-*-*-*-**-**-**-**-**-**-**-**-**-*-**--**----*-**-*-*-*-**-*--*-*--**-**-*-**-**--**-*-**-*-*-----**-*-**-*--"

    Returns: 7128

  39. "-*-**-*--**-**-**-----*---**--*-**-**-*-**--**-**--"

    Returns: 116

  40. "---*-*-**-**-**-*--*-*--**-**-*-**-*-*-**-**-*--*--**-----*-*--**-**-**-**-**--**-**-*--**-**--**--*-*-*--**-*-**-**-**--**-**-*-**--*-**-*--"

    Returns: 63360

  41. "-**----*--**-**-**--**-*--*-**-**-*-**--"

    Returns: 30

  42. "-**-*-**---**-*-*--**---**-**---*--**--**---*-*-*-*--**-**--*-*--*-**-*-*---*-*-*--*-**--*-**--**-**--*---**-**---*-**-**--*--"

    Returns: 1944000

  43. "-**-**-**-**--*----**-**-*--*-*--*-**-**-*---*-*-**-*-**--**-*---*-**--**---------*---**-*-**----*-**-**--**--*----*--*-**----**-**-**-*-**-**-**--*--*-*---*---"

    Returns: 472399678

  44. "--**-*-*-*-**-*--*-**-**-**-*-**--**-**---**--**--"

    Returns: 6

  45. "--*-*-*--**--*-**-*---**-*--*-*-**--**--**-*-*-**-*--*-*-**-*--*--**-*-*---*-----*--*-*--**--**--**-*-*-**--*-*-*-*---**-*--"

    Returns: 5002560

  46. "-*-**-**-*-**-*-**-*--*--*--"

    Returns: 13

  47. "-**-**-*--**-----*-**-*-*----**-*-**-**--**--*-*--*----**--**-**-**--**--*-*-*--**-**-**-**-*-**--**--**-**-**-*--"

    Returns: 33792

  48. "-*-**-*-**-**-*-*--*--**-**-*-*-**-*-**-**---*-**--*--**-*-*----**-*-**--**---*---*-**-*--*-**--**-**-*----*-**--*---**-**-*-*-----*-*-**-*-**-*-*-*---"

    Returns: 24166350

  49. "---*-**-**-**-*--**--**---**-----**-*---**---**--"

    Returns: 504

  50. "-**-*-*-*-**--*-**-*--**--**-*----*--*-*---**-*--*--*-**-**-*-**-**-*--*--**-*-**-**--**--**--"

    Returns: 11520

  51. "-*---**-*--**--*--*-**-**--*---*-*-**--*--*-----*--*--**---**-**-**-*-*-*-*-*-*-*-**---*-**-**-**-*-*-*-*--**-**-**-**--*--"

    Returns: 2704320

  52. "-**--*-*-**--*----*-**-*-**--*--*---*-**-**-**---*-**--**-**-*-**-**-*-*-**-**-*-**--**-**-----*-**-*-*-**-**--"

    Returns: 20790

  53. "--**-**-**--"

    Returns: 1

  54. "-**-*-*-*-*-**--*-**-**-**--**-**-**--*-*--**-*-*-**-**-*-**-**-**-**-**-*-**-**-**--*-*-*-*-**-**--"

    Returns: 16

  55. "-*---*-*-**-**-*--*-*--**-**-*-**-*-**-**---**----*-**-*-*---**-**-*--*--**--*---*----*--*--**-**-**--*-**---------**-**-**--*-**-**-*-*--**---**-**--**-*--*-**-*-*-*--*--*--"

    Returns: 511964282

  56. "-**--**-*-*-**-**--**-**--*---**-**-**-**---**--**-*-**--**--**---**-*-*--**-**--**-**--**-**-*-*-*-*-*-*--*-*-*-*-**-**--**-*-**-*-*-*---**---**-*-**-*-**-**-*-*--"

    Returns: 1440

  57. "-**--**--**--*--*-*-**-*-**-*-**-*-------*-*-**-*--*-**-*-**-*---*-**----*--**-**-**-**-**--"

    Returns: 42750

  58. "----**----*-*-**---**--*-**-*---*--**-*-**-**-*-*-**---**--*-**-*-*---**-**---**-*-*-*-**-**--**-**-*-**-*---**-**-**---*-**-*--"

    Returns: 331776

  59. "-*-**-*-**-**-*-*--*--**-**-*-*-**-*-**-**---*-**--*--**-*-*----**-*-**--**---*---*-**-*--*-**--**-**-*--*-*-**--*---**-**-*-*-----*-*-**-*-**-*-*-*---"

    Returns: 8055450

  60. "--*--**---*-**--**-*-*-*-*-**-**-**-**-**-**-**-**-**-*-**--**----*-**-*-*-*-**-*--*-*--**-**-*-**-**--****-**-*-*-----**-*-**-*--"

    Returns: 0

  61. "-*---**-*--**--*--*-**-**--*---*-*-**--*--*-----*--*--**---**-**-****-*-*-*-*-*-*-**---*-**-**-**-*-*-*-*--**-**-**-**--*--"

    Returns: 0

  62. "-**----*--**-**-**--**-*--****-**-*-**--"

    Returns: 0

  63. "-**----*--**-*****--**-*--*-**-**-*-**--"

    Returns: 0

  64. "-**----*--**-**-***-**-*--*-**-**-*-**--"

    Returns: 0

  65. "-**-**-*--**---*-*-**-*-*----**-*-**-**--**--*-*--*----**--**-**-**--**--*-*-*--**-**-**-**-*-**--**--**-**-**-*--"

    Returns: 9216

  66. "-**-*-**--*---**-*-*--*-**--**-*-*-*-*-**-**--*--**--**-**-*-**-**-*--*-*-**-**--"

    Returns: 135

  67. "-***-**-**--"

    Returns: 0

  68. "-**-***--*-*-**-**--**-*--**-*----**--"

    Returns: 0

  69. "-**----*--*****-**--**-*--****-**-*-**--"

    Returns: 0

  70. "-**----*--*****-**--**-**-****-**-*-**--"

    Returns: 0

  71. "-**-*-*-*-**--*-**-*--**--**-*----*--*-*---**-*--*--*-*****-*-**-**-*--*--**-*-**-**--**--**--"

    Returns: 0

  72. "-**-**-**-**-----*-**-*-*----**-*-**-**--**--*-*--*----**--**-**-**--**--*-*-*--**-**-**-**-*-**--**--**-**-**-*--"

    Returns: 16896

  73. "-*--**--**-*--*-**--*-**-*-**-*--**-*-*-**-**--*-*-**-*-*-**-**--**--**--*-*-*-**-**--*---**-**---*-**-**-**-*-*-*--**-*-**-**-**-**-*-**-**-**-"

    Returns: 2880

  74. "---*-*---**-**-*-**-*--*-*--**--*--*--*----**-**-*--*-**-*-**-**--**----**-*-**--**--**--*----*--**-*--**-**-**--**-**-*-**-**--**-*-*-**---*-*-*-*-**-*-**---**--*-**-*--*-**-**--*--"

    Returns: 237945600

  75. "---***-**-**-**-*--*-*--**-**-*-**-*-*-**-**-*--*--**-----*-*--**-**-**-**-**--**-**-*--**-**--**--*-*-*--**-*-**-**-**--**-**-*-**--*-**-*--"

    Returns: 0

  76. "-*--**--**-*--*-**--*-**-*-**-*--**-*-*-**-**--*-*-**-*-*-**-**--**--**--*-*-*-**-**--*---**-**---*-**-**-**-*-*-*--**-*-*****-**-**-*-**-**-**-"

    Returns: 0

  77. "--*-**-*-****-*-**-*-*-**--*-**----*-*-**-**--*-**-*---**-**-*-*---**-*-**-**-*-**-*-**-**---**--"

    Returns: 0

  78. "-*--**--**-*--*-**--*-**-*-**-*--**-*-*-**-**--*-*-**-*-*-**-**--**--**--*-*-*-**-**--*---**-**---*-**-**-**-*-*-*--**-*-**-**-**-**-*-**-*****-"

    Returns: 0

  79. "--------------------------------------------------------*--------------*------------------------------------"

    Returns: 332479209

  80. "------------------------------------------------------------------*---------------------*-------------------------------------------*----------------------------------------"

    Returns: 293754738

  81. "-------*---*------------------------------------------------------------------------------------------------*-----------------------------------------"

    Returns: 83890944

  82. "----------------------------------------------------------------------------------------------------"

    Returns: 92295268

  83. "---*----------------------------------------------------------------------------------------------------------------------------------------*--------------------"

    Returns: 190898320

  84. "-----------------------------------------------------------*--------------------------------------------------*-------------------------------------------------------------"

    Returns: 502528645

  85. "------------------------------------------------------------------------------------------------------------------------------------*---------------------------------"

    Returns: 609401982

  86. "---------*----------------------------------------------------*---------------------------------------------------------------------------------------------"

    Returns: 119249972

  87. "-------------------------------------------------------------------------------------------*--------------------------------------------------------------*---------------------------------"

    Returns: 790430242

  88. "---------------------------------------------------*------------------------------------------------------------------------------------------------*----------------------"

    Returns: 189005554

  89. "-----------------*--------------------------------------------------------------------------------------"

    Returns: 548851426

  90. "-----------------------------------------------*---------------------------*------------------------------------"

    Returns: 822088685

  91. "-------------------------*---------------------------------------*-------------------------------------------------------------------------*-------------------------"

    Returns: 586085211

  92. "--------------------------------------------------------------------------------------*------------------------------------------------------------------------------------------------------"

    Returns: 114067698

  93. "-----------------------------*----------------------------------------------------------------------------------------------------------------------------------"

    Returns: 198450281

  94. "--------------------------------------------------------------------------*----------------*---------------------------------------------------------------------------------*---"

    Returns: 644348489

  95. "-------------------------------------------------------------------*-------------------------------------------------------------------------------------------------------"

    Returns: 958976168

  96. "-----------*-------------------------------------------------------------------------------------------------------------------------------------*----------------------"

    Returns: 183897296

  97. "-------------------------------------------------------------------*----------------------------------*------------------------------*-----"

    Returns: 573377891

  98. "------------------------------*--------------------------------------------------------------------------------------------------------------------------------------------------"

    Returns: 346763564

  99. "---*-*--*---*----*------------------------------------------------------------------------------------------------------------------------------------------------------------------**--**---**----**---"

    Returns: 234580825

  100. "------------------------------------*------------------------------------**---*------*-----*-------------------------------------*-"

    Returns: 28396614

  101. "------------------------------------*------------------------------------**---*------*-----*--------------------------------------"

    Returns: 129703796

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: