Statistics

Problem Statement for "SumPyramid"

Problem Statement

A sum pyramid is a two-dimensional arrangement of numbers into a pyramid-like shape in which each number (except for the numbers in the bottom row) is the sum of the two numbers that are diagonally below its place. Here's an example of a sum pyramid: 

      25
   12   13
 7    5    8

Note that 12 = 7+5, 13 = 5+8, and 25 = 12+13.

Each row of the sum pyramid is called a level. The sum pyramid shown above has three levels. Note that the number of elements in the bottom row is equal to the number of levels.

You are given the ints levels and top. Consider all sum pyramids with the following properties:

  • All numbers in the pyramid are nonnegative integers.
  • The pyramid has levels levels.
  • The number on the top of the pyramid is top.

Compute and return the number of such pyramids, modulo 10^9 + 7.

Definition

Class:
SumPyramid
Method:
countPyramids
Parameters:
int, int
Returns:
int
Method signature:
int countPyramids(int levels, int top)
(be sure your method is public)

Constraints

  • levels will be between 1 and 1000, inclusive.
  • top will be between 0 and 1000, inclusive.

Examples

  1. 1

    47

    Returns: 1

    In this case the only valid pyramid is just the single number 47.

  2. 2

    10

    Returns: 11

    Three of the eleven valid pyramids: 10 10 10 10 0 4 6 1 9

  3. 3

    2

    Returns: 4

    The four pyramids look as follows: 2 2 2 2 2 0 1 1 1 1 0 2 2 0 0 1 0 1 0 1 0 0 0 2

  4. 5

    7

    Returns: 18

  5. 7

    815

    Returns: 160478559

  6. 8

    990

    Returns: 773698570

  7. 6

    697

    Returns: 613993800

  8. 10

    917

    Returns: 884242392

  9. 554

    832

    Returns: 1393

  10. 903

    232

    Returns: 233

  11. 4

    0

    Returns: 1

  12. 372

    592

    Returns: 1037

  13. 5

    720

    Returns: 121903681

  14. 9

    746

    Returns: 736882732

  15. 866

    342

    Returns: 343

  16. 1

    1

    Returns: 1

  17. 5

    1000

    Returns: 448070112

  18. 3

    2

    Returns: 4

  19. 9

    635

    Returns: 245496142

  20. 259

    99

    Returns: 100

  21. 9

    994

    Returns: 521367250

  22. 245

    828

    Returns: 3410

  23. 692

    893

    Returns: 1300

  24. 12

    1000

    Returns: 103036065

  25. 9

    1000

    Returns: 763519115

  26. 3

    1

    Returns: 2

  27. 12

    683

    Returns: 10135404

  28. 572

    588

    Returns: 625

  29. 384

    733

    Returns: 1436

  30. 7

    520

    Returns: 241623438

  31. 10

    779

    Returns: 277767336

  32. 2

    1

    Returns: 2

  33. 35

    574

    Returns: 32515

  34. 6

    792

    Returns: 147649033

  35. 7

    907

    Returns: 869173437

  36. 5

    732

    Returns: 130142464

  37. 792

    426

    Returns: 427

  38. 2

    2

    Returns: 3

  39. 4

    1

    Returns: 2

  40. 224

    482

    Returns: 1114

  41. 569

    944

    Returns: 1699

  42. 5

    783

    Returns: 169901424

  43. 11

    718

    Returns: 41071636

  44. 11

    661

    Returns: 24212808

  45. 37

    128

    Returns: 570

  46. 1

    0

    Returns: 1

  47. 10

    870

    Returns: 606297720

  48. 1000

    0

    Returns: 1

  49. 9

    905

    Returns: 838038828

  50. 981

    247

    Returns: 248

  51. 5

    532

    Returns: 36901575

  52. 12

    767

    Returns: 19935858

  53. 6

    762

    Returns: 949817869

  54. 10

    1000

    Returns: 659293026

  55. 1

    3

    Returns: 1

  56. 6

    1000

    Returns: 607937230

  57. 3

    0

    Returns: 1

  58. 12

    621

    Returns: 5928774

  59. 268

    365

    Returns: 564

  60. 8

    512

    Returns: 154852630

  61. 11

    960

    Returns: 289866525

  62. 7

    700

    Returns: 316079985

  63. 620

    361

    Returns: 362

  64. 11

    790

    Returns: 76818146

  65. 10

    504

    Returns: 15211669

  66. 705

    361

    Returns: 362

  67. 950

    715

    Returns: 716

  68. 9

    982

    Returns: 63608709

  69. 861

    746

    Returns: 747

  70. 2

    3

    Returns: 4

  71. 781

    200

    Returns: 201

  72. 4

    2

    Returns: 3

  73. 294

    900

    Returns: 3150

  74. 12

    763

    Returns: 19333074

  75. 616

    350

    Returns: 351

  76. 342

    100

    Returns: 101

  77. 6

    631

    Returns: 377748800

  78. 7

    714

    Returns: 474634651

  79. 665

    892

    Returns: 1351

  80. 5

    680

    Returns: 97239321

  81. 393

    520

    Returns: 779

  82. 8

    500

    Returns: 133545935

  83. 6

    675

    Returns: 524901860

  84. 937

    957

    Returns: 1002

  85. 8

    552

    Returns: 248181934

  86. 7

    1000

    Returns: 345692072

  87. 12

    726

    Returns: 14421861

  88. 1

    2

    Returns: 1

  89. 3

    3

    Returns: 6

  90. 11

    617

    Returns: 15742850

  91. 245

    807

    Returns: 3200

  92. 792

    829

    Returns: 908

  93. 11

    1000

    Returns: 386094178

  94. 8

    1000

    Returns: 508496153

  95. 8

    837

    Returns: 586538607

  96. 763

    112

    Returns: 113

  97. 2

    0

    Returns: 1

  98. 1000

    1000

    Returns: 1005

  99. 4

    3

    Returns: 6

  100. 10

    969

    Returns: 318615441

  101. 100

    100

    Returns: 105

  102. 7

    614

    Returns: 621360157

  103. 5

    5

    Returns: 10

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: