<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>

class Solution:  # 812 ms, faster than 66.67%
    def colorTheGrid(self, m: int, n: int) -> int:
        """
        Quite interesting: m <= 5.
        Seems like: you could simply swap all of the colors and get something divisible by 6.

        Therefore: WLOG, you could force the top left to be red, then multiply by 6. Seems kind of challenging—look at example 2.
        
        Suppose m = 1.
        [c1, c2/c3, c2/c3, ...] => 3 * 2 * 2... = 3 * 2^{n-1}.
        
        Now, suppose m = 2. Then: the second row depends on the choices for the first row, as well as the values below.
        
        Consider a triangle: if two colors the same, get two possible; otherwise, deterministic.
            c1
        c1  c2/c3
        
            c1
        c2  c3
        
        The problem: A and B hard to compute
        A[i][j] := number of ways to generate with same value on top and to the left.
        B[i][j] := number of ways to generate with the different values on top and to the left
        dp[i][j] = 2 * A[i][j] + B[i][j].
        
        A[i][j] := 
                
        m = 2, n = 2
        
        3 * 2 * 2
                [c1, c2, c1] OR [c1, c2, c3]
        
        [c2, c3, c2]
        [c2, c1, c2/c3]
        [c3, c1, c2/c3]
        
        
        [c2, c1, c2]
        [c2, c3, c1/c2]
        [c3]
        
        [c2, c1]
        [c3,]
        
        [c2, c1/c3]

        [c3, ]
        
        dp[currentCell][prevColumn][i][j]: # ways of generating currentcell = this color at position ij + previous column 

        """
        def getColor(mask, pos):  # Get color of the `mask` at `pos`, use 2 bits to store a color
            return (mask >> (2 * pos)) & 3
        
        def setColor(mask, pos, color):  # Set `color` to the `mask` at `pos`, use 2 bits to store a color
            return mask | (color << (2 * pos))

        def dfs(r, curColMask, prevColMask, out):
            if r == m:  # Filled full color for this column
                out.append(curColMask)
                return
            for i in [1, 2, 3]:  # Try colors i in [1=RED, 2=GREEN, 3=BLUE]
                if getColor(prevColMask, r) != i and (r == 0 or getColor(curColMask, r - 1) != i):
                    dfs(r + 1, setColor(curColMask, r, i), prevColMask, out)

        @lru_cache(None)
        def neighbor(prevColMask):  # Generate all possible columns we can draw, if the previous col is `prevColMask`
            out = []
            dfs(0, 0, prevColMask, out)
            return out

        @lru_cache(None)
        def dp(c, prevColMask):
            if c == n: return 1  # Found a valid way
            ans = 0
            for nei in neighbor(prevColMask):
                ans = (ans + dp(c + 1, nei)) % 1_000_000_007
            return ans

        return dp(0, 0)
36700