Colouring a Three-Column Strip

Hard

A strip of rows rows and 3 columns is painted with three colours: each cell gets exactly one colour, and no two cells sharing a side (horizontally or vertically) may have the same colour. Count such colourings. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

rows=1 → 12

Three cells in a row: the first takes any of 3 colours, each next one any of the other 2: 3 · 2 · 2 = 12.

Example 2

rows=2 → 54

Example 3

rows=3 → 246

Constraints

1 ≤ rows ≤ 5000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Water Between Walls Hard Does the Text Fit the Pattern Hard Biggest Solid Panel Block Hard

Input

rows=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 39 tests on the server, hidden ones included.