Number of Ways to Paint N × 3 Grid

This solution uses dynamic programming built on a key insight: any valid coloring of a single 3-cell row falls into one of two shapes — an ABA pattern (the two outer cells share a color, like Red-Yellow-Red) or an ABC pattern (all three cells differ), and there are exactly 6 of each for the first row, giving the starting values A = 6 and B = 6. Counting how one row can sit on top of another shows that a row below an ABA row can be one of 3 ABA + 2 ABC patterns, while a row below an ABC row allows 2 of each — which yields the recurrences newA = 2 * A + 2 * B and newB = 2 * A + 3 * B. The loop applies these transitions once per additional row, keeping every value reduced modulo 10^9 + 7 to avoid overflow, and the final answer is simply (A + B) % MOD. By tracking only two aggregate counts instead of enumerating actual grids, it runs in O(n) time with O(1) memory — a massive improvement over the exponential backtracking approach.