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)


CONSTRAINTS
-w will be between 1 and 10, inclusive.
-h will be between 1 and 10, inclusive.


EXAMPLES

0)
1
3

Returns: 4



1)
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.

2)
3
2

Returns: 84

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

3)
4
9

Returns: 132976888

4)
5
5

Returns: 11676046

 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)2010, TopCoder, Inc. All rights reserved.