Number of Ways to Paint N × 3 Grid

Compress rows by pattern type

A valid three-cell row with adjacent colors different is either ABA (two colors) or ABC (three distinct colors). At row one there are six of each type. Instead of storing literal colors, track counts aba and abc. For the standard three-color problem, the next values are nextAba = 3*aba + 2*abc and nextAbc = 2*aba + 2*abc, with all arithmetic modulo the required modulus.

The recurrence works because color permutations make all rows of the same pattern type equivalent; the coefficients count compatible next rows. Iterate from row two through n, then return aba + abc. Runtime is O(n) and auxiliary space is O(1). Test n = 1, a small hand-enumerated n = 2, and large n for modular overflow. Do not use a 27-state DP unless explaining it as a valid but uncompressed baseline, and do not forget the horizontal adjacency restriction when classifying rows.