1411. Number of Ways to Paint N × 3 Grid

Paint an n×3 grid with 3 colours so no two side-adjacent cells share a colour; count the valid colourings mod 1e9+7. The elegant reduction: a valid row of 3 cells is only ever one of two types —…