Hard

Quiz

#1411 Number of Ways to Paint N × 3 Grid

APPROACH

You have an n x 3 grid to color with three colors (Red, Yellow, Green) so that no two horizontally or vertically adjacent cells share a color. Given n, return the number of valid colorings modulo 10⁹ + 7.

Example 1:

Input: n = 1

Output: 12

Explanation: There are 12 possible way to paint the grid as shown.

Example 2:

Input: n = 5000

Output: 30228214

1 of 4

1:00

What is the optimal approach for this problem?