Statistics

Problem Statement for "Spacetsk"

Problem Statement

The spaceport is a horizontal segment of length L. We are planning to launch a rocket from the spaceport. The rocket must fly in a straight line. The line does not have to be orthogonal to the spaceport, but it must lie in the vertical plane that contains the spaceport. The line is not allowed to be strictly horizontal.

Each point in the vertical plane has two coordinates: the x-coordinate is the horizontal distance from the left end of the spaceport, and the y-coordinate is the altitude above the spaceport. Points for with both coordinates are integers are called grid points.

The rocket has to be launched from a grid point on the spaceport. Moreover, after the launch the rocket must send exactly K signals. A signal can only be sent when the rocket is at a grid point above the spaceport, and its altitude does not exceed H.

Formally: The rocket starts from one of the points (x,0), where 0 <= x <= L and x is an integer. The rocket may send a signal if it is at one of the points (x,y), where 0 <= x <= L, 0 <= y <= H, and x and y are both integers. The rocket may only send at most one signal at each grid point it passes through.



The picture above shows two different test cases. The grid on the left corresponds to L=9, H=7, and K=2. Each of the six colors shows one pair of signals you could observe during the launch. The small grids on the right show all four possibilities for L=1, H=1, and K=2.

You are given the ints L, H, and K. Count how many different sets of signals are possible during the launch. Return the answer modulo 1,000,000,007.

Definition

Class:
Spacetsk
Method:
countsets
Parameters:
int, int, int
Returns:
int
Method signature:
int countsets(int L, int H, int K)
(be sure your method is public)

Constraints

  • L will be between 1 and 2000, inclusive.
  • H will be between 1 and 2000, inclusive.
  • K will be between 1 and 2000, inclusive.

Examples

  1. 1

    1

    2

    Returns: 4

    Example from the statement.

  2. 1

    1

    1

    Returns: 4

  3. 2

    2

    1

    Returns: 9

  4. 2

    2

    2

    Returns: 23

  5. 10

    8

    6

    Returns: 1502

  6. 2000

    2000

    1000

    Returns: 151877339

  7. 2000

    2000

    2000

    Returns: 4008005

  8. 1

    2000

    2000

    Returns: 4002

  9. 2000

    1

    2000

    Returns: 0

  10. 1

    1

    2000

    Returns: 0

  11. 2000

    2000

    1

    Returns: 4004001

  12. 1

    2000

    1

    Returns: 4002

  13. 2000

    1

    1

    Returns: 4002

  14. 5

    5

    3

    Returns: 202

  15. 2000

    2000

    314

    Returns: 697236322

  16. 2000

    2000

    373

    Returns: 524773139

  17. 2000

    2000

    374

    Returns: 90861865

  18. 2000

    2000

    348

    Returns: 133105885

  19. 2000

    2000

    1602

    Returns: 547379130

  20. 2000

    2000

    530

    Returns: 468926091

  21. 2000

    2000

    139

    Returns: 226608514

  22. 2000

    2000

    784

    Returns: 834860813

  23. 2000

    2000

    1702

    Returns: 539949376

  24. 2000

    2000

    1560

    Returns: 471514789

  25. 1867

    1090

    1377

    Returns: 0

  26. 962

    724

    1919

    Returns: 0

  27. 1393

    466

    1482

    Returns: 0

  28. 1830

    1428

    1131

    Returns: 233464949

  29. 1870

    652

    1418

    Returns: 0

  30. 1378

    1494

    271

    Returns: 509157650

  31. 1212

    876

    1990

    Returns: 0

  32. 1413

    1100

    1790

    Returns: 0

  33. 1410

    1319

    473

    Returns: 759489792

  34. 751

    1729

    1477

    Returns: 587260833

  35. 743

    758

    38

    Returns: 175069635

  36. 1741

    1698

    54

    Returns: 359322791

  37. 1538

    699

    19

    Returns: 110941280

  38. 121

    129

    44

    Returns: 277897384

  39. 1289

    854

    52

    Returns: 393053037

  40. 561

    394

    20

    Returns: 786097180

  41. 4

    557

    83

    Returns: 37451909

  42. 1949

    1609

    86

    Returns: 891710326

  43. 895

    271

    15

    Returns: 643898239

  44. 89

    1985

    43

    Returns: 364811797

  45. 1

    1

    2

    Returns: 4

  46. 1

    1

    1

    Returns: 4

  47. 1

    2

    2

    Returns: 10

  48. 1

    3

    1

    Returns: 8

  49. 1

    4

    4

    Returns: 10

  50. 1

    5

    4

    Returns: 30

  51. 2

    1

    1

    Returns: 6

  52. 2

    2

    1

    Returns: 9

  53. 2

    3

    3

    Returns: 14

  54. 2

    4

    4

    Returns: 15

  55. 2

    5

    4

    Returns: 45

  56. 3

    1

    1

    Returns: 8

  57. 3

    2

    1

    Returns: 12

  58. 3

    3

    1

    Returns: 16

  59. 3

    4

    2

    Returns: 100

  60. 3

    5

    5

    Returns: 24

  61. 4

    1

    1

    Returns: 10

  62. 4

    2

    1

    Returns: 15

  63. 4

    3

    2

    Returns: 106

  64. 4

    4

    3

    Returns: 88

  65. 4

    5

    4

    Returns: 87

  66. 5

    1

    1

    Returns: 12

  67. 5

    2

    2

    Returns: 90

  68. 5

    3

    1

    Returns: 24

  69. 5

    4

    1

    Returns: 30

  70. 5

    5

    1

    Returns: 36

  71. 1998

    2000

    2

    Returns: 746070084

  72. 1990

    1991

    3

    Returns: 896157189

  73. 2000

    1998

    4

    Returns: 264942267

  74. 1999

    1997

    5

    Returns: 306008222

  75. 1990

    1994

    6

    Returns: 309815717

  76. 1995

    1999

    7

    Returns: 664934527

  77. 1991

    1999

    8

    Returns: 740213095

  78. 1998

    1993

    9

    Returns: 81009664

  79. 1996

    1998

    10

    Returns: 30757729

  80. 1991

    1990

    11

    Returns: 14560881

  81. 1995

    1995

    12

    Returns: 586486438

  82. 2000

    1991

    13

    Returns: 10635526

  83. 1997

    1999

    14

    Returns: 224456032

  84. 1990

    1998

    15

    Returns: 107528861

  85. 1992

    1991

    16

    Returns: 404514335

  86. 1992

    1992

    17

    Returns: 135572620

  87. 1999

    1996

    18

    Returns: 682532160

  88. 1997

    1999

    19

    Returns: 588574456

  89. 2000

    1992

    20

    Returns: 676778405

  90. 2000

    2000

    7

    Returns: 362865718

  91. 2000

    2000

    15

    Returns: 273697280

  92. 2000

    2000

    3

    Returns: 703376456

  93. 2000

    2000

    17

    Returns: 304227118

  94. 2000

    2000

    100

    Returns: 371115391

  95. 1231

    1456

    54

    Returns: 884788862

  96. 2000

    2000

    10

    Returns: 770655607

  97. 2000

    2000

    5

    Returns: 515716267

  98. 2000

    2000

    2

    Returns: 827908596

  99. 2000

    2000

    32

    Returns: 987308232

  100. 2000

    2000

    13

    Returns: 846997

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: