Question
You must paint every cell of a grid that has 3 columns and n rows. Each cell is painted one of three colors (red, yellow, green). No two adjacent cells in the same row may share a color, and no two vertically adjacent cells (same column, consecutive rows) may share a color. Return the number of ways to paint the whole grid, modulo 1000000007. n is between 1 and 5000.
num_ways_paint(n: int) → int[1]out12State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
Vibe coding: describe the solution in plain language (or narrate it) and the coach grades your approach. Generating runnable code from your description is coming next.