TopCoder Statistics - Problem Statement

Problem Statement

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

We have a set of many construction bricks. It contains exactly one base which is simply a special kind of brick of dimensions 1x1xw. We also have a infinite amount of bricks of k different kinds: 1x1x1, 1x1x2, ..., 1x1xk. Formally, for each i between 1 and k, inclusive, we have as many 1x1xi bricks as we need. For simplicity, we will call these bricks "bricks of length i". The following image shows the situation for w=9 and k=3: there is a base of length 9, and three brick types of lengths 1, 2, and 3.

We can stack bricks on top of other bricks (including the base) to form different structures. The design of the bricks forces us to place the bricks at integer positions only. To ensure stability, each brick other than the base must rest completely on a surface composed of other bricks or the base. The following image shows a structure that is invalid for four 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 three ints: w, the length of the base, k, the maximum length of your bricks, and h, the maximum height of your structure. Find the total number of different valid structures you can make. Return the total modulo 1000000007.

For example, the following image shows all 83 different valid structures when w = 3, k = 3 and h = 2.

Definition

Class:: BricksN
Method:: countStructures
Parameters:: int, int, int
Returns:: int
Method signature:: int countStructures(int w, int h, int k)
(be sure your method is public)

Constraints

w and h will each be between 1 and 50, inclusive.
k will be between 1 and w, inclusive.

Examples

3

1

3

Returns: 13

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

2

3

Returns: 83

This is the example from the statement.
1

5

1

Returns: 6
10

10

3

Returns: 288535435
1

1

1

Returns: 2
50

50

50

Returns: 92324271
50

1

50

Returns: 782204094
50

50

1

Returns: 370141234
1

50

1

Returns: 51
24

11

13

Returns: 226244183
42

31

34

Returns: 145616060
33

7

17

Returns: 903406539
24

23

19

Returns: 226815126
20

22

6

Returns: 671975329
39

31

32

Returns: 581268661
33

16

15

Returns: 447266089
40

5

32

Returns: 532852082
18

4

5

Returns: 892978442
32

1

24

Returns: 680051485
44

24

18

Returns: 652699350
47

21

3

Returns: 595660426
47

18

38

Returns: 577142937
28

27

4

Returns: 838449365
36

12

20

Returns: 293540022
35

40

2

Returns: 923407699
32

6

30

Returns: 455215822
40

26

29

Returns: 81640412
29

11

25

Returns: 946776653
27

43

12

Returns: 928823009
26

33

21

Returns: 936515743
43

15

23

Returns: 675733855
24

24

2

Returns: 671739533
39

14

16

Returns: 481294962
21

25

19

Returns: 218730215
12

49

5

Returns: 179229393
45

6

38

Returns: 164259191
39

35

18

Returns: 548296079
46

15

27

Returns: 91927671
10

44

7

Returns: 735940928
15

10

14

Returns: 482084640
49

6

36

Returns: 914876095
44

22

34

Returns: 701421808
45

29

27

Returns: 318744893
40

40

33

Returns: 312758978
42

24

29

Returns: 289635826
47

26

35

Returns: 447902488
39

10

17

Returns: 374614459
41

12

22

Returns: 834618603
35

21

4

Returns: 482134196
33

39

7

Returns: 864607600
48

38

48

Returns: 211888061
18

5

1

Returns: 955957503
36

2

1

Returns: 246336683
20

27

14

Returns: 928370940
20

35

14

Returns: 340463923
35

43

11

Returns: 86378826
43

41

18

Returns: 55222538
27

6

26

Returns: 147049069
44

16

10

Returns: 68964478
48

40

44

Returns: 939938014
30

5

28

Returns: 859768457
40

11

1

Returns: 216720791
44

27

22

Returns: 565058815
48

38

25

Returns: 952655565
29

20

17

Returns: 272635618
33

21

32

Returns: 48682013
46

49

46

Returns: 417794594
27

44

6

Returns: 956155233
35

21

33

Returns: 497283773
47

24

46

Returns: 919491080
28

25

17

Returns: 788105544
29

29

7

Returns: 345872887
20

47

18

Returns: 385728449
15

34

3

Returns: 886405943
32

3

17

Returns: 926357119
29

17

9

Returns: 679582522
43

22

21

Returns: 161481729
9

7

3

Returns: 952392526
47

32

20

Returns: 407959737
49

4

44

Returns: 295972292
39

34

5

Returns: 311372000
33

44

14

Returns: 915333816
5

50

2

Returns: 402339917
23

11

20

Returns: 326809311
42

32

18

Returns: 912682929
24

5

24

Returns: 674935388
44

9

6

Returns: 881367659
21

19

13

Returns: 550761840
49

23

8

Returns: 445590405
19

7

1

Returns: 67049563
39

27

21

Returns: 759152641
35

3

31

Returns: 254887395
5

26

5

Returns: 601868906
47

10

25

Returns: 344837176
49

1

42

Returns: 94206927
46

7

11

Returns: 998595812
42

6

34

Returns: 553996431
26

40

1

Returns: 761890566
47

25

13

Returns: 34799949
27

46

16

Returns: 305181494
48

31

32

Returns: 39006546
44

21

14

Returns: 435658969
38

22

29

Returns: 837893796
32

29

16

Returns: 859361536
24

9

6

Returns: 644523200
30

22

30

Returns: 89419870
50

5

3

Returns: 420042817
39

29

20

Returns: 31507160
7

16

2

Returns: 206268304
46

18

27

Returns: 206101859
37

19

6

Returns: 369521450
19

13

14

Returns: 114341966
25

3

9

Returns: 113819288
31

46

15

Returns: 144830604
31

9

20

Returns: 975887637
8

21

1

Returns: 875873158
44

48

44

Returns: 942955760
34

14

8

Returns: 472763486
49

18

31

Returns: 170587802
46

48

15

Returns: 871992056
49

4

36

Returns: 366419017
43

34

5

Returns: 904465261
38

44

11

Returns: 917275057
33

47

11

Returns: 816381674
44

41

19

Returns: 623651007
38

7

14

Returns: 911507767
30

38

24

Returns: 638196420
49

3

44

Returns: 823185529
35

10

1

Returns: 526144858
43

44

1

Returns: 168971720
1

27

1

Returns: 28
42

38

8

Returns: 891983609
48

25

19

Returns: 85042131
40

16

8

Returns: 572621259
24

42

5

Returns: 101904761
22

33

12

Returns: 577676589
16

1

12

Returns: 3524513
43

33

40

Returns: 329294845
30

47

5

Returns: 337637190
39

36

36

Returns: 49889383
35

6

10

Returns: 410250815
26

14

4

Returns: 670451582
31

18

28

Returns: 265222851
37

49

32

Returns: 362916534
46

42

35

Returns: 787110412
35

37

29

Returns: 16373381
22

15

9

Returns: 687480309
42

3

25

Returns: 715579780
48

5

9

Returns: 557998430
45

8

35

Returns: 520607305
48

12

26

Returns: 960540959
30

13

7

Returns: 176027878
35

22

12

Returns: 384377688
47

10

10

Returns: 895646169
40

34

5

Returns: 73943471
33

36

6

Returns: 78747156
30

47

9

Returns: 398957235
49

34

44

Returns: 742371065
11

26

3

Returns: 368382950
48

50

40

Returns: 40308775
47

50

41

Returns: 92850214
45

47

24

Returns: 860893795
49

47

30

Returns: 591335981
46

46

33

Returns: 840110311
47

50

14

Returns: 632295723
48

45

8

Returns: 784839805
50

45

43

Returns: 6088545
48

48

17

Returns: 793179184
48

47

46

Returns: 254760344
45

46

40

Returns: 222861600
50

45

21

Returns: 361656963
48

45

48

Returns: 840227117
50

47

41

Returns: 447089850
47

49

39

Returns: 238972955
49

46

42

Returns: 74798210
46

45

17

Returns: 578814225
47

49

40

Returns: 80475345
45

49

21

Returns: 92903800
48

48

4

Returns: 282743411
48

47

2

Returns: 242208060
45

50

18

Returns: 533936012
47

46

5

Returns: 87692265
47

49

45

Returns: 590164755
49

48

43

Returns: 852486670
50

48

42

Returns: 971818323
46

45

16

Returns: 133553480
48

45

22

Returns: 661433485
49

45

38

Returns: 979969099
47

47

43

Returns: 756499746
45

49

27

Returns: 254416013
50

49

47

Returns: 116403450
50

50

27

Returns: 607410160

Statistics

Problem Statement for "BricksN"

Problem Statement

Definition

Constraints

Examples