<p>You are given two integers <code>m</code> and <code>n</code>. Consider an <code>m x n</code> grid where each cell is initially white. You can paint each cell <strong>red</strong>, <strong>green</strong>, or <strong>blue</strong>. All cells <strong>must</strong> be painted.</p>

<p>Return<em> the number of ways to color the grid with <strong>no two adjacent cells having the same color</strong></em>. Since the answer can be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/colorthegrid.png" style="width: 200px; height: 50px;" />
<pre>
<strong>Input:</strong> m = 1, n = 1
<strong>Output:</strong> 3
<strong>Explanation:</strong> The three possible colorings are shown in the image above.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/copy-of-colorthegrid.png" style="width: 321px; height: 121px;" />
<pre>
<strong>Input:</strong> m = 1, n = 2
<strong>Output:</strong> 6
<strong>Explanation:</strong> The six possible colorings are shown in the image above.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> m = 5, n = 5
<strong>Output:</strong> 580986
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= m &lt;= 5</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

from enum import Enum
from functools import cache

MOD = int(1e9 + 7)

class Color(Enum):
    R = 0
    G = 1
    B = 2


def generate_possible_column_fills(m, filled = []) -> List[List[Color]]:
    """Generate all the possible ways to fill a single column with size m"""
    if len(filled) == m:
        return [filled]
    results = []
    for c in Color:
        if filled and filled[-1] == c:
            continue
        results.extend(generate_possible_column_fills(m, filled + [c]))
    return results

def try_match(cols) -> List[List[int]]:
    """Try match columns to each other.

    Assumes:
        all columns are valid. I.e.
            col[j] != cols[i][j+1] for all col in cols for all j < m-1
    
    Returns:
        a list "matched", where len(matched) == len(cols) and
        matched[i] is a list [j1, j2, j3, ...] with indices to all columns that would match
        cols[i]. Where a "match" means they can be neighbors. There will be no two adjacent
        cells having the same color. I.e.
            cols[i][k] != cols[j][k] for all k < m and for all j in matched[i]
    """
    def match(col1, col2):
        return all(a != b for a, b in zip(col1, col2))

    ncols = len(cols)
    result = []
    for i in range(ncols):
        result.append([])
    for i in range(ncols):
        for j in range(i+1, ncols):
            if match(cols[i], cols[j]):
                result[i].append(j)
                result[j].append(i)
    return result



class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        all_possible_columns = generate_possible_column_fills(m)
        col_match_table = try_match(all_possible_columns)

        @cache
        def n_possible_col_fill(filled_col_idx, n_cols_to_fill):
            """Returns the number of possible ways to fill a grid.

            Args:
                filled_col_idx: the index to some known column lists (all_possible_columns).
                    This col is considered already filled into the grid, and is neighbor to 
                    the first empty column to be filled.
                n_cols_to_fill: number of *remaining* columns to fill. The filled column is *not*
                    included.
                col_match_table: a list of list of indices. col_match_table[i] include all indices
                    of columns that can be neighbor of column i, all these indices are to some known
                    column lists (all_possible_columns)
            """
            if n_cols_to_fill == 0:
                return 1
            answer = 0
            for icol in col_match_table[filled_col_idx]:
                answer = (answer + n_possible_col_fill(icol, n_cols_to_fill - 1)) % MOD
            return answer
        answer = 0
        for icol in range(len(all_possible_columns)):
            answer = (answer + n_possible_col_fill(icol, n-1)) % MOD
        return answer
        
494