A Grid in Three Colors

Hard

You have a grid with rows rows and cols columns. Every cell must be painted red, green or blue, and cells that share a side must get different colors. Return the number of ways to paint the grid. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

rows=1, cols=3 → 12

The first cell has 3 choices and each next one has 2: 3 · 2 · 2 = 12.

Example 2

rows=2, cols=2 → 18

The first column can be colored in 6 ways, and each fits exactly 3 choices for the second column: 18.

Example 3

rows=3, cols=4 → 1122

Constraints

1 ≤ rows ≤ 5
1 ≤ cols ≤ 1000

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, cols=3

Expected

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