Statistics

Problem Statement for "SkyscraperCounting"

Problem Statement

There are N skyscrapers built in a row. The bases of all N skyscrapers all stand on one line that goes from the west to the east.

Each skyscraper has between 1 and N floors, inclusive. No two skyscrapers have the same number of floors.


An observer is looking at the row of skyscrapers from an observation point that is far to the west from all of them. For this observer, some skyscrapers are at least partially visible while others are completely invisible. More precisely, a skyscraper floor is visible to the observer if and only if no skyscraper to the west of this one has a floor of the same height.


Below is one sample scene. Arrows ("->") indicate the direction in which we look at the skyscrapers (west is on the left of the figure). There are seven skyscrapers, each shown as one column of 'X's and 'O's. Floors visible to the observer are shown as 'O', floors hidden behind other skyscrapers are shown as 'X'. 


->                   O
->                   O  X
->          O        X  X
->          O  X     X  X
->    O     X  X     X  X
->    O     X  X  X  X  X
->    O  X  X  X  X  X  X
=============================

You are given the String visibility with N characters. For each skyscraper, from the west to the east, this String contains either the character 'O' (uppercase oh) or the character 'X'. The character 'O' represents a skyscraper with some visible floors, the character 'X' a skyscraper with no visible floors.

For the sample scene shown above, visibility = "OXOXXOX".


In other words, visibility tells you what the scene with skyscrapers looks when viewed from above. For each skyscraper, from the left to the right, you are told whether its topmost floor is 'O' (visible from the west) or 'X' (hidden behind another skyscraper when looking from the west).


Count all permutations of skyscrapers that correspond to the given String visibility. Return that count modulo (10^9 + 7).

Definition

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

Constraints

  • visibility will have between 1 and 100 characters, inclusive.
  • Each character in visibility will be either 'O' or 'X'.

Examples

  1. "OXXXX"

    Returns: 24

    We can deduce that the leftmost skyscraper must be the tallest one (5 floors). Each of the 4! = 24 orders of the other four skyscrapers works.

  2. "OXOXXOX"

    Returns: 72

    This input corresponds to the figure in the problem statement. The skyscrapers shown in the figure have heights {3, 1, 5, 4, 2, 7, 6}, and this is one of the 72 permutations of heights that produce the given visibility pattern. Some of the other permutations with the same visibility pattern: {3, 1, 5, 2, 4, 7, 6} {2, 1, 5, 3, 4, 7, 6} {4, 3, 6, 5, 1, 7, 2}

  3. "XOXOXO"

    Returns: 0

    No such permutations: the westmost skyscraper is always visible.

  4. "OXXXXXXXXXXXXXO"

    Returns: 227020758

    Remember to compute the answer modulo 10^9 + 7.

  5. "OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: 104379182

  6. "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"

    Returns: 1

  7. "OXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXOXXO"

    Returns: 105944501

  8. "OXXXOX"

    Returns: 30

  9. "OXOOXO"

    Returns: 4

  10. "OOXXOO"

    Returns: 6

  11. "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"

    Returns: 1

  12. "XOOXOOOOOOOOOOOOOOOOOOOOOXOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOO"

    Returns: 0

  13. "OXOOOOOXOOOOOOOXOOOOOOOXOOOOOOOOOXOOOOOOOXOOOOOXOOOOOOOXOOOOOOOOOOXOOOOOOXXOOO"

    Returns: 452093834

  14. "OXOOOOXOOOXOXXXXOOXOOOOXOOXOOOOOXOXOOOOOOXOXOOOXOOXOOOOOOXXOOOOOOOXOOOO"

    Returns: 205417843

  15. "OOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"

    Returns: 15

  16. "OXXOXXOXXXOOXXOOXXOXOXXXXXOOXXXOXOXXXOOXOOOOXOXXXOXOXOXXXXOOXXXOOXOOXXXXXXXXOXOXXXXOOXOXOOOXXXX"

    Returns: 108987402

  17. "OOOOOXXXXOOOOOXOOXOOXOOOOOOOXXXOOOXXOXXXXXOXOOOXOOOOOXOXOXOXOOOXOOOOOOXXOXOOOOOOOXXXXOOOXOOO"

    Returns: 233382053

  18. "OOOOOOOOOOOOOXXOOOXOXXOXOOOOOXOOOOOXOOOOOOOOOOOOXOOOOOOOOOOOXOOOXOOOXOO"

    Returns: 158858636

  19. "OXXOOOX"

    Returns: 12

  20. "OXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX"

    Returns: 228919597

  21. "OOXXOXOOOOOOOOOXOOOOOOXOOXOOOOXOOXXOOOOOOOOOOOOOXOOOOOOOOOOXOOOXXOOOXXOOOOOOOOOXO"

    Returns: 930492857

  22. "OOXOXOOOOOOXOOOXOOOOOOOOXXOXXXOXOOOOXXOOOOXOOOOOOOOOXOXOOOXOXOXOOXOOOOOXXOOOOOO"

    Returns: 477318963

  23. "OOOXOO"

    Returns: 3

  24. "OXX"

    Returns: 2

  25. "OOOOXOOOOOOOOOOOOOOXOXOOOXOOOOOOOOXOOOOOOXOOOOOOXOOOOOOOOOOOOXOOOOOOOOOO"

    Returns: 857115666

  26. "X"

    Returns: 0

  27. "OXOOXOOOOOOOOXOOOOXXXXOOOXXOOOXOXOOXOOOOOOOOXOXXOOXOOOOXOXXXOOOOOOXOOOXXXOOOOOOOOOOXOOOXOXOOX"

    Returns: 638640114

  28. "XOOOXOOOOOOXXOOOOOXXXXOOOOOOXXOXOOOOXOXOOOOOXOXXOOXOXOOOXOOXOOXXXXOOOOOOO"

    Returns: 0

  29. "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOO"

    Returns: 79

  30. "OOXXXX"

    Returns: 120

  31. "OOOXOOOOXXOXOOXOOXXXXOOOOOOXXOOXXOOOXOXXOOOOOOOOOXXOOOOOOOOOOOOOOOOXOOOXXOOXOOXOOOOOXOOOOOO"

    Returns: 231167027

  32. "OXXOXXXXOOXOXXXXXXXOOXXXXXXOOXXOXXXXXXXOXXXXXOOXXXOOXXXXXXXXXXXXXXXXXOXXOOXXXXXOXXXOOOXXOXXX"

    Returns: 374291117

  33. "OOOXXXXOXOXXOXOOOXOXXXXOXOXXXOXXXXXXOXOXXXXXXXXXXXXOXOXXXXXXXXOOXXXOXOXXXOOOXXXOXOOXO"

    Returns: 225151140

  34. "OXXXXXXXXXXXXXOXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXOXOXXXXXX"

    Returns: 266289630

  35. "OOOOOOOOOOOXOOOOOOXXOXXOOOOXOXXXOXOXOOOOXOOXXOOOOXXOOOOOOXOOOOOOOOOOOOXOOXO"

    Returns: 500704093

  36. "OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXXXXXXXOX"

    Returns: 49025421

  37. "OXXXXOOXXXOXXXOXXXXXXXOXXXOXXXXXXOXXXXXXOXXXXXXXXOOXXXXXXOXXXXXXOOXXOXXXXXXXOOXX"

    Returns: 859978373

  38. "OXXOXXXOXXXXOOXOXOOOXOXOOXOXXXOOXXXXXOXXOOOXXXOXXXXOOXXXOOXXOXXOXXXXXXXOXXXXXXOXXXX"

    Returns: 853423337

  39. "OOOOOOOXOOOOOOOOOOOOXOOOXXOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOXOOOOOOOOOOO"

    Returns: 371539909

  40. "OOXXXXOOXOXOXOXOXOOXOOOOXOXOOOOXXXXXOOXOOOOXXXOOXXOXXXOXXOXXXXOXOOXXXXXXOOXXOOOX"

    Returns: 822590313

  41. "OOOOOXOOOOOOOXOXOXOXOOOOOOOXOXOOXOOOOOOXOOOXXOOOOOOXXOOOOXOOOOOOOOOXOOOOOOXO"

    Returns: 142763330

  42. "XOOXXXOOXOOOXOOXOOXXOXOXOOXXOOXOXOOOXOXXXXOXXXOXXXOXXXOOXXXOOOXXXOOOXOXXOXXOXXXOOXXO"

    Returns: 0

  43. "OOXOOXOXXXXXOXXXOOOOXXOXXXOXXXXXXXXXXOOOXOXXXXOOOOOXXXOOXOXXOXOXXOOXOOOOXOOOOXXOOOOXOXXXOOXOO"

    Returns: 314219880

  44. "OOXOXOX"

    Returns: 48

  45. "OXXXOXXXXXXOXOXOOXXOXXOXXXOXOXXXOOXXXOXXOXXXOXOXOXOXXXOXXXXXXXXXXXXXXXXOXOOOXXXXXXXXOXXOXXXXXOXX"

    Returns: 310098171

  46. "OOXXO"

    Returns: 6

  47. "OXOOXXOOOOOOOXOOXOOXOXOOOOOXOOXXXXXXOOOOOOXOOOOXOOOOXXOOOOOOXOOOOOOOOOXOXXOOOOXOOOOXOXOXOOOXOXOOXX"

    Returns: 481185397

  48. "OXXXXO"

    Returns: 24

  49. "XOOXOOOOXOOXOXXOOXXOXOXOOXXXXOXXXOXOXOXXXXXOXOXXXXXOOOXOOOOOOOXXXXOXXOOOXOOOOOOOXOXXOOOOO"

    Returns: 0

  50. "XOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"

    Returns: 0

  51. "OXO"

    Returns: 1

  52. "OXOXOXXXXOXXXXXOXOXXXXXXXXXXXXOXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXOOXXXXXXXXXXXXXXOXXXXXXXXXXXXOXXX"

    Returns: 561927869

  53. "OOOOXXX"

    Returns: 120

  54. "OOXOOO"

    Returns: 2

  55. "OOOXXXXOOXOXXXOXXXXOOXXXOXOOOOXOXOXXXOXXXXXOXOXOOXOXXOOXOXXXXXXXOXOOXXOXXOOXOOOXOOO"

    Returns: 100850489

  56. "OXXXXXOOXOXXOOOOXXXXOXOXOXXOXOOXXOOOOXXXOOXXOXXOXXXXOOXOOXXXOOOOXOXXXXXOXXXOXOXOXXXXXX"

    Returns: 68349499

  57. "OOOOOOOXOXXOXXXXOOOOOOXOOXOOXXXOXOOOOOOXOOXXOOXXOOOOOXOXOXXOOOOXOOOXXOXOXOOXOOOOOXXXOO"

    Returns: 330075457

  58. "OOOOOOXOXOXOOOXOOXOOOXOOOOOXOOXXOOOOOOOXOXOXXOOOXXOOXOXOOXOOXOOXOOXOXOXXO"

    Returns: 528383062

  59. "OOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOO"

    Returns: 806

  60. "OXXXOOXXXXXOOXOOXOOOOXOOOOXXOXXXXXOOOOOOOOOOOXXXXXXOXOOXXOXOOXXXOOOXOOOOXXOOOOXOOXOOOXOOOXOXOXOXOOO"

    Returns: 898504613

  61. "OXXOXXOXXXOOOOXOXOOXXXXOOOOXOXXXXXXOOOOOXXXXOOXOXOOXOOOOXOOOXOOXOXOOXXOXXXOX"

    Returns: 219596409

  62. "OXOOOXXOOXXXOOXXOXXOXOOXXXOOOOOOXOXOXOOXOOOOXXXOXOOOOOXOXOOXOXXXXOXOXOXXXXXOOXOOXXOX"

    Returns: 606066226

  63. "XXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXX"

    Returns: 0

  64. "OOOXO"

    Returns: 3

  65. "OOXX"

    Returns: 6

  66. "OXXOXOXXXOOXXOOXXOXXXXXOOXXXOXXOXXXXXOOOOXOXXXXXOXOXXOOXXOXXXOXOXXXOXOXXXXXO"

    Returns: 922297494

  67. "OOOOOOOXOXOOOXOOXXXOOOOOOOXOOXXXXOXOXXXOOOOXXXOOOXOOXXOXOOXXOOOOXOOOOOOOXXXXXOXXO"

    Returns: 161287357

  68. "XOOOOOXOOXOOOXOOXOOOOOOOOOOOOOXXOOOOOOOOXOXOXOOOOOOOOOXOOXOOXOXOXOXOOOXOOOOXOOXOXXXXXOXOX"

    Returns: 0

  69. "OXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXX"

    Returns: 586060270

  70. "OOOOX"

    Returns: 4

  71. "OXOXXOXXOXXXXXOOXXXXXXXXXXXXXOXXOOXXXXOXXXXXXXXXXXXXXXXXXXXXXOXXOXXOXXXXOXXXOXXXXXXXXXXXXXXXOXX"

    Returns: 963682702

  72. "OXXXOXOXXXXXXXXOOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOOXXOOXXXXXXXXXXXXXXXXXXXXXX"

    Returns: 460187880

  73. "OOXOOXXXXXXXXXXXXXXOXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXOOXXXXXXOXO"

    Returns: 901717150

  74. "OO"

    Returns: 1

  75. "XOOXOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOO"

    Returns: 0

  76. "OOO"

    Returns: 1

  77. "OX"

    Returns: 1

  78. "OOXXX"

    Returns: 24

  79. "OXOXXXOXXXOXXXXXXXXXXXOXXXXOOXXXXXXXXOXXXXXXOXOXOXXXXXXOXXXXXXXXXXXXOXXXX"

    Returns: 882993412

  80. "OOOXXXXXOXOOXXXXOOXOXXXXOXOXXOOOXOXOOOXXOXOXOOOOOXXXOOOXOXXOXXOOXXXXOXXOXOOOOXOOXXOOXXXXO"

    Returns: 547898954

  81. "OXOOOOOOOXOOOOOOXOOXOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOXOXOOOOOXXOOOOOOOOOOOOOOOOOOXOOOOOOXOXOX"

    Returns: 963315912

  82. "OXXOOOO"

    Returns: 2

  83. "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOXOOOOOXOOOOOOOOOXOOO"

    Returns: 603727993

  84. "XOXXOOXOOOOOOOOOOOXOXOOOOOXXOOXOXOOOOOOOOOXOOOOOOOOOXOOOOOOOOOOOOOOOOOOXOXOOOOOOOOXOXOOOXOOOOOOOOXO"

    Returns: 0

  85. "OOXXXOXXOOXXXOOOXXOXXOXXOXXXOXOOXXOOXXXOXXXXXXXXOXOOOXXXOOOXOXXXXOOXXXXXOXXXOOXXOXOOO"

    Returns: 708837468

  86. "XOOOOOOOOOXOOOOOOOXOOOOOXOOOOOOOOOXOOOOOOOXOOOOOOOOXOXOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOO"

    Returns: 0

  87. "OOX"

    Returns: 2

  88. "OXOXXXXXOXXXXOOXXXOOXOXXXXXXOOXOOOXXXOOXOXXXXXXXOXXXXXXXOXXOXXXXOXXXOOXXXOOXXOOXXXXOXXXXXOXXOO"

    Returns: 992645792

  89. "OXOOOXOXOOOXOOOOOOOOOOOOXXOOOOXOOXOXXOOOOOXOXOOOOOOXOXXOXOXOXOXOOXOOXOOXXOXXOOOOXOOXOOOOOXXX"

    Returns: 59971954

  90. "O"

    Returns: 1

  91. "OXOOO"

    Returns: 1

  92. "OXXOXXXXOXOXXXXOXXXXXXXOXXXOXXXOXXXXXXOXOXOOXOOXXXXOXXOXXXXOXXXXXOXXXOXOXOXXXOXOXOXXOOOOXXOXXXXXXXOO"

    Returns: 832368478

  93. "OXXOXXO"

    Returns: 40

  94. "OXOXOXOXOXOXXOXOXOXOXOXXOXOXOXOXOXXOXOXOXOXOX"

    Returns: 488912801

  95. "OOXXXOXXXOXOXOXXOXOXXOXOOXXXXOXOXXXOOXOXXXXOOOXXXXOOOOXOOXXOXXOXOOXXOOOOXXOXXOOOXOOOXOOOOXXXXXXOOXO"

    Returns: 509730714

  96. "OXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOXOX"

    Returns: 196932377

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: