The most readable solution without bitmask (and beats 73%)!
Intuition\nThere are at most 5 rows. So there are at most $3\cdot2^4 = 48$ possible ways to fill a column. This problem can be simplified to this: choose with r
# Intuition\nThere are at most 5 rows. So there are at most $3\\cdot2^4 = 48$ possible ways to fill a column. This problem can be simplified to this: choose with repitition $n$ columns from a set of columns such that no adjacent cells have the same color.\n\nConsidering filling the grid from left to right column by column. The choice of the $i^{th}$ column should only depend on $(i-1)^{th}$ column, but not any column before that. And since there are at most 48 possible choices of columns, we can precompute all the columns that can be neighbors. This way the problem is further simplified to: given a set of columns, and a table that for each possible column all possible columns you can choose next, find the number of possible ways to choose n columns.\n\n# Approach\n1. find all possible ways to fill columns without adjacent same color tile, name it `all_possible_cols`.\n2. for each column in `all_possible_cols`, find all possible columns that can be put next to it. The result will be a table `match_table` where $j\\in match_table[i] \\iff$ `all_possible_cols[i]` and `all_possible_cols[j]` can be neighbors.\n3. start with each of `all_possible_cols` as the first column in the grid, recursively calculate the possible ways to fill a grid.\n\n# Complexity\n- Time complexity:\nIt takes $O(c^m)$ to calculate all possible columns. Then to find the `match_table`, it squared the number of possible columns, so $O(c^{2m})$.\nFinally the recursive call (DFS) with cache, is about $O(c^mn)$. Since m is small and c is small, this can be considered $O(n)$.\n\n- Space complexity:\nThe recursion makes it a bit hard to approximate the space complexity.\n    * all possible columns take $O(c^mm)$ space.\n    * match table takes $O(C^{2m})$ space. Maybe it\'s less. What\'s the order for the number of candidates a column with length $m$ can have?\n    * the recursive call takes $O(c^mn)$ space for the cache. The stack for the recursive call is $O(n)$.\nOverall the space complexity is $O(c^mn)$ ~ $O(n)$ given small c and m.\n\n# Code\n```\nfrom enum import Enum\nfrom functools import cache\n\nMOD = int(1e9 + 7)\n\nclass Color(Enum):\n    R = 0\n    G = 1\n    B = 2\n\n\ndef generate_possible_column_fills(m, filled = []) -> List[List[Color]]:\n    """Generate all the possible ways to fill a single column with size m"""\n    if len(filled) == m:\n        return [filled]\n    results = []\n    for c in Color:\n        if filled and filled[-1] == c:\n            continue\n        results.extend(generate_possible_column_fills(m, filled + [c]))\n    return results\n\ndef try_match(cols) -> List[List[int]]:\n    """Try match columns to each other.\n\n    Assumes:\n        all columns are valid. I.e.\n            col[j] != cols[i][j+1] for all col in cols for all j < m-1\n    \n    Returns:\n        a list "matched", where len(matched) == len(cols) and\n        matched[i] is a list [j1, j2, j3, ...] with indices to all columns that would match\n        cols[i]. Where a "match" means they can be neighbors. There will be no two adjacent\n        cells having the same color. I.e.\n            cols[i][k] != cols[j][k] for all k < m and for all j in matched[i]\n    """\n    def match(col1, col2):\n        return all(a != b for a, b in zip(col1, col2))\n\n    ncols = len(cols)\n    result = []\n    for i in range(ncols):\n        result.append([])\n    for i in range(ncols):\n        for j in range(i+1, ncols):\n            if match(cols[i], cols[j]):\n                result[i].append(j)\n                result[j].append(i)\n    return result\n\n\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        all_possible_columns = generate_possible_column_fills(m)\n        col_match_table = try_match(all_possible_columns)\n\n        @cache\n        def n_possible_col_fill(filled_col_idx, n_cols_to_fill):\n            """Returns the number of possible ways to fill a grid.\n\n            Args:\n                filled_col_idx: the index to some known column lists (all_possible_columns).\n                    This col is considered already filled into the grid, and is neighbor to \n                    the first empty column to be filled.\n                n_cols_to_fill: number of *remaining* columns to fill. The filled column is *not*\n                    included.\n                col_match_table: a list of list of indices. col_match_table[i] include all indices\n                    of columns that can be neighbor of column i, all these indices are to some known\n                    column lists (all_possible_columns)\n            """\n            if n_cols_to_fill == 0:\n                return 1\n            answer = 0\n            for icol in col_match_table[filled_col_idx]:\n                answer = (answer + n_possible_col_fill(icol, n_cols_to_fill - 1)) % MOD\n            return answer\n        answer = 0\n        for icol in range(len(all_possible_columns)):\n            answer = (answer + n_possible_col_fill(icol, n-1)) % MOD\n        return answer\n        \n```
['Python3']