<p>You have a <code>grid</code> of size <code>n x 3</code> and you want to paint each cell of the grid with exactly one of the three colors: <strong>Red</strong>, <strong>Yellow,</strong> or <strong>Green</strong> while making sure that no two adjacent cells have the same color (i.e., no two cells that share vertical or horizontal sides have the same color).</p>

<p>Given <code>n</code> the number of rows of the grid, return <em>the number of ways</em> you can paint this <code>grid</code>. As the answer may grow large, the answer <strong>must be</strong> computed modulo <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/2020/03/26/e1.png" style="width: 400px; height: 257px;" />
<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 12
<strong>Explanation:</strong> There are 12 possible way to paint the grid as shown.
</pre>

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

<pre>
<strong>Input:</strong> n = 5000
<strong>Output:</strong> 30228214
</pre>

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

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>1 &lt;= n &lt;= 5000</code></li>
</ul>

from math import comb
import numpy as np
from itertools import chain, permutations, product
class Solution:
    def numOfWays(self, n: int) -> int:
        l1 = []

        q = [[1],[2],[3]]

        while q:
            el = q.pop()
            if len(el) == 3:
                l1.append((el[0], el[1], el[2]))
            else:
                match el[-1]:
                    case 1:
                        q.append(el + [2])
                        q.append(el + [3])
                    case 2:
                        q.append(el + [1])
                        q.append(el + [3])
                    case 3:
                        q.append(el + [1])
                        q.append(el + [2])
    
        print(l1)

        # l1 = list(filter(lambda x: x[0] != x[1] != x[2], product([1,2,3], repeat=3)))
        
        pairs = {}
        for el in l1:
            for el2 in l1:
                if el[0] != el2[0] and  el[1] != el2[1] and  el[2] != el2[2]:  
                    if el in pairs:
                        pairs[el].add(el2)
                    else:
                        pairs[el] = set([el2])
               
        mem = {}
        def count(e, depth=1):
            if (e, depth) in mem:
                return mem[(e, depth)]
            if depth == n:
                return 1
            else:
                mem[(e, depth)] = sum([count(el, depth+1) for el in pairs[e]]) % ((1e9) + 7)
                return mem[(e, depth)]

        return int(sum([count(e, 1) for e in l1])  % ((1e9) + 7))

51000