Statistics

Problem Statement for "RowOfColors"

Problem Statement

George has a grid of w columns and h rows. He plans to color each cell of the grid using one of k different available colors. There are some rules he plans to follow:
  • The top-most row must contain at least one cell of each of the k colors.
  • Every pair of cells of the same color must be connected. Two cells are connected if there is a path between them that consists of cells that share a common edge and are of the same color.
Find the number of different valid ways to color the top-most row. Two ways to color the top-most row are different if and only if at least one of the cells in the top-most row has a different color. For each different coloring of the top-most row, there may be many valid ways to color the rest of the grid, but we will only count that coloring exactly once. Since the result may be very big, return the number of ways modulo 1000000007.

Definition

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

Constraints

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

Examples

  1. 4

    1

    2

    Returns: 6

    There is only one row in the grid. The 6 different ways to color the grid with 2 different colors such that the cells of each color are connected are: "AAAB", "AABB", "ABBB", "BBBA", "BBAA" and "BAAA".

  2. 4

    3

    2

    Returns: 12

    This time "ABAA", "AABA", "ABBA", "BABB", "BBAB" and "BAAB" are new valid ways to color the top-most row in the grid. The following are some of the grid colorings that allow those top rows: ABAA AABA ABBA BABB BBAB BAAB ABBA AAAA ABAA BABB BAAB BBBB AAAA AAAA AAAA BBBB BBBB BBBB

  3. 4

    4

    10

    Returns: 0

    It is impossible to use each of the 10 different colors on the 4 cells in the top row.

  4. 14

    28

    14

    Returns: 178290591

  5. 100

    20

    25

    Returns: 148201539

  6. 4

    4

    3

    Returns: 36

    AABC ABAC ABCA ABCC ABCB ABBC

  7. 300

    300

    300

    Returns: 419467694

  8. 300

    300

    150

    Returns: 784197416

  9. 1

    1

    1

    Returns: 1

  10. 2

    300

    2

    Returns: 2

  11. 300

    10

    2

    Returns: 89700

  12. 300

    10

    3

    Returns: 996224679

  13. 150

    74

    75

    Returns: 631942245

  14. 150

    10

    75

    Returns: 756243307

  15. 300

    1

    147

    Returns: 745868737

  16. 100

    7

    24

    Returns: 7310839

  17. 240

    289

    262

    Returns: 0

  18. 50

    35

    44

    Returns: 732596863

  19. 33

    48

    111

    Returns: 0

  20. 64

    12

    212

    Returns: 0

  21. 23

    44

    279

    Returns: 0

  22. 69

    84

    21

    Returns: 349451876

  23. 44

    101

    108

    Returns: 0

  24. 12

    149

    206

    Returns: 0

  25. 75

    111

    258

    Returns: 0

  26. 58

    190

    10

    Returns: 251750298

  27. 23

    181

    115

    Returns: 0

  28. 27

    153

    209

    Returns: 0

  29. 56

    224

    299

    Returns: 0

  30. 69

    281

    6

    Returns: 666592259

  31. 42

    254

    112

    Returns: 0

  32. 42

    267

    195

    Returns: 0

  33. 49

    270

    293

    Returns: 0

  34. 76

    2

    61

    Returns: 392856899

  35. 147

    71

    104

    Returns: 667244272

  36. 136

    4

    179

    Returns: 0

  37. 111

    28

    272

    Returns: 0

  38. 121

    87

    32

    Returns: 752328292

  39. 128

    79

    97

    Returns: 436881882

  40. 97

    124

    198

    Returns: 0

  41. 142

    103

    296

    Returns: 0

  42. 126

    203

    35

    Returns: 168905624

  43. 116

    176

    94

    Returns: 787125160

  44. 91

    181

    185

    Returns: 0

  45. 137

    165

    278

    Returns: 0

  46. 116

    231

    38

    Returns: 242502939

  47. 144

    271

    117

    Returns: 512482209

  48. 104

    237

    170

    Returns: 0

  49. 135

    281

    283

    Returns: 0

  50. 198

    41

    46

    Returns: 309050308

  51. 157

    16

    134

    Returns: 316099124

  52. 203

    70

    170

    Returns: 180783538

  53. 200

    45

    257

    Returns: 0

  54. 185

    128

    61

    Returns: 266243489

  55. 175

    83

    106

    Returns: 467212189

  56. 218

    135

    157

    Returns: 214012640

  57. 165

    127

    241

    Returns: 0

  58. 215

    165

    71

    Returns: 694950986

  59. 151

    223

    118

    Returns: 253059109

  60. 221

    183

    220

    Returns: 282811922

  61. 174

    221

    276

    Returns: 0

  62. 157

    255

    14

    Returns: 269282528

  63. 205

    259

    104

    Returns: 463350099

  64. 221

    292

    194

    Returns: 836143583

  65. 182

    236

    248

    Returns: 0

  66. 228

    43

    73

    Returns: 881055729

  67. 255

    58

    139

    Returns: 210659146

  68. 296

    4

    197

    Returns: 47260663

  69. 263

    5

    237

    Returns: 157284222

  70. 290

    116

    20

    Returns: 519880426

  71. 239

    121

    150

    Returns: 172734297

  72. 268

    116

    208

    Returns: 663458666

  73. 292

    108

    236

    Returns: 576228657

  74. 270

    184

    45

    Returns: 797104041

  75. 283

    152

    120

    Returns: 273810281

  76. 283

    223

    224

    Returns: 990043966

  77. 265

    188

    244

    Returns: 693927072

  78. 293

    263

    64

    Returns: 621495630

  79. 297

    292

    94

    Returns: 691043977

  80. 254

    232

    225

    Returns: 461509803

  81. 287

    263

    282

    Returns: 630465772

  82. 218

    219

    258

    Returns: 0

  83. 152

    156

    273

    Returns: 0

  84. 289

    274

    287

    Returns: 704322209

  85. 235

    197

    249

    Returns: 0

  86. 207

    191

    195

    Returns: 612845869

  87. 283

    188

    292

    Returns: 0

  88. 285

    160

    197

    Returns: 275490213

  89. 177

    222

    283

    Returns: 0

  90. 217

    213

    290

    Returns: 0

  91. 256

    244

    255

    Returns: 962427540

  92. 286

    240

    285

    Returns: 959444329

  93. 150

    188

    156

    Returns: 0

  94. 246

    172

    206

    Returns: 575248215

  95. 265

    279

    239

    Returns: 877501162

  96. 166

    170

    206

    Returns: 0

  97. 293

    172

    213

    Returns: 47264865

  98. 241

    175

    226

    Returns: 364939486

  99. 279

    231

    189

    Returns: 933587926

  100. 186

    180

    217

    Returns: 0

  101. 176

    199

    249

    Returns: 0

  102. 188

    277

    230

    Returns: 0

  103. 254

    296

    175

    Returns: 842249849

  104. 228

    221

    187

    Returns: 595945492

  105. 265

    230

    260

    Returns: 903420670

  106. 288

    266

    230

    Returns: 159666371

  107. 216

    183

    274

    Returns: 0

  108. 224

    204

    295

    Returns: 0

  109. 258

    158

    238

    Returns: 639378104

  110. 293

    235

    262

    Returns: 447849095

  111. 152

    224

    190

    Returns: 0

  112. 300

    100

    200

    Returns: 95648989

  113. 300

    100

    150

    Returns: 117957987

  114. 298

    276

    299

    Returns: 0

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: