1931. Painting a Grid With Three Different Colors

Grid m×n (rows m ≤ 5, columns up to 1000). Colour each cell one of 3 colours so vertical and horizontal neighbours differ. Count colourings mod 1e9+7. Process column by column: a column's state is a…