Statistics

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:

SpacetskE

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 200, inclusive.
• H will be between 1 and 200, inclusive.
• K will be between 1 and 200, 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. 5

   5

   3

   Returns: 202

6. 10

   8

   6

   Returns: 1502

7. 200

   200

   100

   Returns: 517966361

8. 200

   200

   200

   Returns: 40805

9. 1

   200

   200

   Returns: 402

10. 200

    1

    200

    Returns: 0

11. 1

    1

    200

    Returns: 0

12. 200

    200

    1

    Returns: 40401

13. 1

    200

    1

    Returns: 402

14. 200

    1

    1

    Returns: 402

15. 1

    1

    1

    Returns: 4

16. 200

    200

    114

    Returns: 203920813

17. 200

    200

    173

    Returns: 138294213

18. 200

    200

    174

    Returns: 343589215

19. 200

    200

    148

    Returns: 824534898

20. 200

    200

    2

    Returns: 30011900

21. 200

    200

    130

    Returns: 130039306

22. 200

    200

    139

    Returns: 337785121

23. 200

    200

    184

    Returns: 267368674

24. 200

    200

    102

    Returns: 564238831

25. 200

    200

    160

    Returns: 569965212

26. 67

    90

    177

    Returns: 0

27. 162

    124

    119

    Returns: 909800140

28. 193

    66

    82

    Returns: 0

29. 30

    28

    131

    Returns: 0

30. 70

    52

    18

    Returns: 296314116

31. 178

    94

    71

    Returns: 810454039

32. 12

    76

    190

    Returns: 0

33. 13

    100

    190

    Returns: 0

34. 10

    119

    73

    Returns: 562046293

35. 151

    129

    77

    Returns: 588420568

36. 143

    158

    38

    Returns: 348751250

37. 141

    98

    4

    Returns: 180668731

38. 138

    99

    19

    Returns: 866933792

39. 121

    129

    44

    Returns: 277897384

40. 89

    54

    2

    Returns: 1272918

41. 161

    194

    20

    Returns: 663266971

42. 4

    157

    33

    Returns: 479801757

43. 149

    9

    36

    Returns: 0

44. 95

    71

    15

    Returns: 533591205

45. 89

    185

    43

    Returns: 788690037

46. 1

    1

    2

    Returns: 4

47. 1

    1

    1

    Returns: 4

48. 1

    2

    2

    Returns: 10

49. 1

    3

    1

    Returns: 8

50. 1

    4

    4

    Returns: 10

51. 1

    5

    4

    Returns: 30

52. 2

    1

    1

    Returns: 6

53. 2

    2

    1

    Returns: 9

54. 2

    3

    3

    Returns: 14

55. 2

    4

    4

    Returns: 15

56. 2

    5

    4

    Returns: 45

57. 3

    1

    1

    Returns: 8

58. 3

    2

    1

    Returns: 12

59. 3

    3

    1

    Returns: 16

60. 3

    4

    2

    Returns: 100

61. 3

    5

    5

    Returns: 24

62. 4

    1

    1

    Returns: 10

63. 4

    2

    1

    Returns: 15

64. 4

    3

    2

    Returns: 106

65. 4

    4

    3

    Returns: 88

66. 4

    5

    4

    Returns: 87

67. 5

    1

    1

    Returns: 12

68. 5

    2

    2

    Returns: 90

69. 5

    3

    1

    Returns: 24

70. 5

    4

    1

    Returns: 30

71. 5

    5

    1

    Returns: 36

72. 190

    199

    2

    Returns: 26855972

73. 200

    190

    3

    Returns: 511074661

74. 195

    191

    4

    Returns: 284265981

75. 191

    196

    5

    Returns: 710048046

76. 197

    198

    6

    Returns: 786327441

77. 193

    200

    7

    Returns: 99090937

78. 199

    193

    8

    Returns: 898059212

79. 197

    193

    9

    Returns: 657211695

80. 192

    192

    10

    Returns: 467235665

81. 194

    193

    11

    Returns: 999735483

82. 191

    198

    12

    Returns: 566307093

83. 197

    193

    13

    Returns: 48717751

84. 200

    190

    14

    Returns: 765435022

85. 190

    194

    15

    Returns: 425124561

86. 193

    195

    16

    Returns: 296845581

87. 191

    199

    17

    Returns: 791684200

88. 193

    191

    18

    Returns: 330491041

89. 199

    199

    19

    Returns: 513667931

90. 200

    194

    20

    Returns: 692800612

91. 200

    200

    3

    Returns: 565193480

92. 199

    199

    51

    Returns: 742317626