Statistics

Problem Statement for "StrangeElevator"

Problem Statement

When cat Taro went to an internship, he found a strange elevator in the office's skyscraper. The skyscraper contains 58 floors. The elevator is composed of 2 boxes and these 2 boxes move together. When the lower box stops at the x-th floor, the upper box always stops at the (x+1)-th floor. The lower box stops only on odd floors (1st, 3rd, 5th, ..., 57th). The upper box stops only on even floors (2nd, 4th, 6th, ..., 58th). He is very interested by this elevator, and he wants to compute the number of possible elevators composed of N boxes in a skyscraper of height H.

The elevators must satisfy the following conditions:
  • For each floor, exactly one box stops at that floor.
  • The distance between 2 boxes is an integer and never changes. More formally, for each pair of boxes (A,B), there must be some integer d such that box B always stops at the (x+d)-th floor when box A stops at the x-th floor. If the (x+d)-th floor doesn't exist, box A must not stop at the x-th floor.

Two elevators are different if the following is true. When the bottommost box is at the first floor, there exists an i such that a box is at the i-th floor in one elevator and no box is at the i-th floor in the other elevator. You are given two integers H and N. Return the number of possible elevators that have N boxes in a skyscraper of height H, modulo 1,000,000,007.

Definition

Class:
StrangeElevator
Method:
theCount
Parameters:
int, int
Returns:
int
Method signature:
int theCount(int H, int N)
(be sure your method is public)

Constraints

  • H will be between 1 and 1,000,000,000, inclusive.
  • N will be between 1 and H, inclusive.

Examples

  1. 58

    2

    Returns: 2

    The following two elevators are possible: When the lower box stops at the 1st, 3rd, ..., 57th floor, the upper box stops at the 2nd, 4th, ..., 58th floor, respectively. When the lower box stops at the 1st, 2nd, ..., 29th floor, the upper box stops at the 30th, 31st, ..., 58th floor, respectively.

  2. 1

    1

    Returns: 1

    The only box always stops at the 1st floor.

  3. 9

    3

    Returns: 2

    The following two elevators are possible: When the lowest box stops at the 1st, the 4th and the 7th floor, the middle box stops at the 2nd, the 5th and the 8th floor, and the topmost box stops at the 3rd, the 6th and the 9th floor, respectively. When the lowest box stops at the 1st, the 2nd and the 3rd floor, the middle box stops at the 4th, the 5th and the 6th floor, and the topmost box stops at the 7th, the 8th and the 9th floor, respectively.

  4. 120

    12

    Returns: 30

  5. 58585858

    495

    Returns: 0

  6. 1000000000

    1000000000

    Returns: 1

  7. 1000000000

    100000

    Returns: 46084626

  8. 1000000000

    1

    Returns: 1

  9. 182213016

    143984807

    Returns: 0

  10. 238647758

    190736101

    Returns: 0

  11. 555163223

    250237128

    Returns: 0

  12. 718317798

    468980913

    Returns: 0

  13. 124915584

    94644450

    Returns: 0

  14. 391483374

    34506875

    Returns: 0

  15. 221301889

    28937254

    Returns: 0

  16. 198250703

    65436098

    Returns: 0

  17. 609810568

    192222420

    Returns: 0

  18. 587687201

    501458422

    Returns: 0

  19. 735134400

    1

    Returns: 1

  20. 735134400

    2

    Returns: 1152

  21. 735134400

    4

    Returns: 72900

  22. 735134400

    6

    Returns: 121608

  23. 735134400

    12

    Returns: 2600520

  24. 735134400

    24

    Returns: 18151500

  25. 735134400

    36

    Returns: 17558970

  26. 735134400

    48

    Returns: 51573780

  27. 735134400

    60

    Returns: 34086480

  28. 735134400

    120

    Returns: 138797220

  29. 735134400

    180

    Returns: 126848370

  30. 735134400

    240

    Returns: 252235920

  31. 735134400

    360

    Returns: 337625220

  32. 735134400

    720

    Returns: 420874080

  33. 735134400

    840

    Returns: 359055300

  34. 735134400

    1260

    Returns: 311108580

  35. 735134400

    1680

    Returns: 433013040

  36. 735134400

    2520

    Returns: 551986500

  37. 735134400

    5040

    Returns: 469706280

  38. 735134400

    7560

    Returns: 225436100

  39. 735134400

    10080

    Returns: 182402316

  40. 735134400

    15120

    Returns: 136058760

  41. 735134400

    20160

    Returns: 24983364

  42. 735134400

    25200

    Returns: 184111080

  43. 735134400

    27720

    Returns: 563286180

  44. 735134400

    45360

    Returns: 0

  45. 735134400

    50400

    Returns: 49287108

  46. 735134400

    55440

    Returns: 328268040

  47. 735134400

    83160

    Returns: 149826020

  48. 735134400

    110880

    Returns: 85742724

  49. 735134400

    166320

    Returns: 60891960

  50. 735134400

    221760

    Returns: 7577976

  51. 735134400

    277200

    Returns: 80650680

  52. 735134400

    332640

    Returns: 10728708

  53. 735134400

    498960

    Returns: 0

  54. 735134400

    554400

    Returns: 13879440

  55. 735134400

    665280

    Returns: 599984

  56. 735134400

    720720

    Returns: 139926840

  57. 735134400

    1081080

    Returns: 60769220

  58. 735134400

    1441440

    Returns: 23331636

  59. 735134400

    2162160

    Returns: 15735600

  60. 735134400

    2882880

    Returns: 1208928

  61. 735134400

    3603600

    Returns: 20323320

  62. 735134400

    4324320

    Returns: 1618644

  63. 735134400

    6486480

    Returns: 0

  64. 735134400

    7207200

    Returns: 2028360

  65. 735134400

    8648640

    Returns: 44912

  66. 735134400

    10810800

    Returns: 1295400

  67. 735134400

    14414400

    Returns: 53928

  68. 735134400

    17297280

    Returns: 0

  69. 735134400

    21621600

    Returns: 67464

  70. 735134400

    32432400

    Returns: 0

  71. 735134400

    36756720

    Returns: 2077500

  72. 735134400

    43243200

    Returns: 672

  73. 735134400

    61261200

    Returns: 2600520

  74. 735134400

    73513440

    Returns: 101292

  75. 735134400

    110270160

    Returns: 0

  76. 735134400

    122522400

    Returns: 121608

  77. 735134400

    147026880

    Returns: 896

  78. 735134400

    183783600

    Returns: 72900

  79. 735134400

    245044800

    Returns: 1008

  80. 735134400

    294053760

    Returns: 0

  81. 735134400

    367567200

    Returns: 1152

  82. 735134400

    551350800

    Returns: 0

  83. 735134400

    698377680

    Returns: 0

  84. 735134400

    735134400

    Returns: 1

  85. 840

    840

    Returns: 1

  86. 61261200

    120

    Returns: 3558676

  87. 551350800

    180

    Returns: 71259384

  88. 498960

    332640

    Returns: 0

  89. 221760

    12

    Returns: 24450

  90. 665280

    48

    Returns: 363780

  91. 122522400

    1260

    Returns: 13685940

  92. 32432400

    720

    Returns: 4678080

  93. 14414400

    840

    Returns: 9883100

  94. 294053760

    27720

    Returns: 174730080

  95. 367567200

    10080

    Returns: 12831492

  96. 14414400

    120

    Returns: 5830940

  97. 277200

    840

    Returns: 62668

  98. 498960

    10080

    Returns: 0

  99. 2520

    360

    Returns: 24

  100. 1260

    60

    Returns: 96

  101. 294053760

    45360

    Returns: 0

  102. 21621600

    120

    Returns: 7723620

  103. 367567200

    21621600

    Returns: 576

  104. 61261200

    12

    Returns: 289704

  105. 122522400

    110270160

    Returns: 0

  106. 120

    60

    Returns: 12

  107. 665280

    27720

    Returns: 224100

  108. 551350800

    665280

    Returns: 0

  109. 60

    36

    Returns: 0

  110. 73513440

    720720

    Returns: 494100

  111. 698377680

    720720

    Returns: 494100

  112. 122522400

    110270160

    Returns: 0

  113. 83160

    24

    Returns: 5580

  114. 3603600

    55440

    Returns: 4740

  115. 999999999

    999

    Returns: 52

  116. 10

    1

    Returns: 1

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: