Statistics

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

We have three kinds of construction bricks. Those of dimensions 1x1x1, 1x1x2 and 1x1x3. We also have a special brick of dimensions 1x1xw which we will call the base.



We would like to use the bricks and the base to build structures. For the bricks to connect to each other and to the base, they all have to be aligned properly. Placing a brick at a non-integer position is not allowed. Also, to ensure stability, the longer bricks (1x1x2 and 1x1x3) must be placed in a way that their extremes both rest on top of another brick or bricks, including the base. There may be an empty space directly below the middle part of a 1x1x3 brick. The following image shows a valid structure and the other image shows a structure that is invalid for three reasons.




The height of a structure is the number of layers of bricks it contains. The base is not counted into the height of the structure.

Two structures are different if there is a position where they differ in any way. (There are two ways in which two given structures may differ: First, there may be a position where one structure has a brick and the other does not. Second, there may be a position where both structures have bricks, but the bricks are of different types.)

Given are two ints w and h. Count the total number of different structures that can be created using any number of 1x1x1, 1x1x2 and 1x1x3 bricks and a base of width w such that the height of the structure is at most h units. Since the result can be large, return the count modulo 1000000007.

For example, the following image shows the 84 different structures for w=3, h=2:

Definition

Class:

SmallBricks31

Method:

countWays

Parameters:

int, int

Returns:

int

Method signature:

int countWays(int w, int h)

(be sure your method is public)

Constraints

• w will be between 1 and 10, inclusive.
• h will be between 1 and 10, inclusive.

Examples

1. 1

   1

   Returns: 2

2. 1

   2

   Returns: 3

3. 1

   3

   Returns: 4

4. 1

   3

   Returns: 4

5. 1

   5

   Returns: 6

6. 1

   6

   Returns: 7

7. 1

   7

   Returns: 8

8. 1

   8

   Returns: 9

9. 1

   9

   Returns: 10

10. 1

    10

    Returns: 11

11. 2

    1

    Returns: 5

12. 2

    2

    Returns: 15

13. 2

    3

    Returns: 37

14. 2

    4

    Returns: 83

15. 2

    5

    Returns: 177

16. 2

    6

    Returns: 367

17. 2

    7

    Returns: 749

18. 2

    8

    Returns: 1515

19. 2

    9

    Returns: 3049

20. 2

    10

    Returns: 6119

21. 3

    1

    Returns: 13

    The leftmost column in the picture above shows the 13 different structures of width 3 and at most 1 unit of height.

22. 3

    2

    Returns: 84

    The picture above shows the 84 different structures of width 3 and at most 2 unit of height.

23. 3

    3

    Returns: 429

24. 3

    4

    Returns: 1991

25. 3

    5

    Returns: 8864

26. 3

    6

    Returns: 38737

27. 3

    7

    Returns: 167869

28. 3

    8

    Returns: 724680

29. 3

    9

    Returns: 3122877

30. 3

    10

    Returns: 13446503

31. 4

    1

    Returns: 33

32. 4

    2

    Returns: 436

33. 4

    3

    Returns: 4266

34. 4

    4

    Returns: 36913

35. 4

    5

    Returns: 301887

36. 4

    6

    Returns: 2400844

37. 4

    7

    Returns: 18816786

38. 4

    8

    Returns: 146324359

39. 4

    9

    Returns: 132976888

40. 4

    10

    Returns: 751733376

41. 5

    1

    Returns: 84

42. 5

    2

    Returns: 2300

43. 5

    3

    Returns: 44157

44. 5

    4

    Returns: 739194

45. 5

    5

    Returns: 11676046

46. 5

    6

    Returns: 179653089

47. 5

    7

    Returns: 730115178

48. 5

    8

    Returns: 237973525

49. 5

    9

    Returns: 21034400

50. 5

    10

    Returns: 82403180

51. 6

    1

    Returns: 214

52. 6

    2

    Returns: 12152

53. 6

    3

    Returns: 457949

54. 6

    4

    Returns: 14817059

55. 6

    5

    Returns: 450472846

56. 6

    6

    Returns: 324032071

57. 6

    7

    Returns: 24861902

58. 6

    8

    Returns: 170708663

59. 6

    9

    Returns: 587048789

60. 6

    10

    Returns: 81051310

61. 7

    1

    Returns: 545

62. 7

    2

    Returns: 64063

63. 7

    3

    Returns: 4723781

64. 7

    4

    Returns: 294027079

65. 7

    5

    Returns: 107928446

66. 7

    6

    Returns: 839339396

67. 7

    7

    Returns: 761082424

68. 7

    8

    Returns: 728312256

69. 7

    9

    Returns: 9546377

70. 7

    10

    Returns: 648669217

71. 8

    1

    Returns: 1388

72. 8

    2

    Returns: 337944

73. 8

    3

    Returns: 48819580

74. 8

    4

    Returns: 858831727

75. 8

    5

    Returns: 504677840

76. 8

    6

    Returns: 381017248

77. 8

    7

    Returns: 831713243

78. 8

    8

    Returns: 583941925

79. 8

    9

    Returns: 536794181

80. 8

    10

    Returns: 933406633

81. 9

    1

    Returns: 3535

82. 9

    2

    Returns: 1782740

83. 9

    3

    Returns: 504494117

84. 9

    4

    Returns: 697109537

85. 9

    5

    Returns: 868971794

86. 9

    6

    Returns: 379952655

87. 9

    7

    Returns: 791371725

88. 9

    8

    Returns: 365989229

89. 9

    9

    Returns: 82390183

90. 9

    10

    Returns: 281959639

91. 10

    1

    Returns: 9003

92. 10

    2

    Returns: 9403676

93. 10

    3

    Returns: 212349446

94. 10

    4

    Returns: 517627099

95. 10

    5

    Returns: 951030965

96. 10

    6

    Returns: 147316164

97. 10

    7

    Returns: 468172153

98. 10

    8

    Returns: 554967316

99. 10

    9

    Returns: 28066586

100. 10

     10

     Returns: 951846687