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

def ternary (n):
    if n == 0:
        return '0'
    nums = []
    while n:
        n, r = n//3, n%3
        nums.append(str(r))
    return ''.join(reversed(nums))

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        dp = [[0 for j in range(3**m)] for i in range(n)]
        ans = 0
        mapping = {'0':{0:'1',1:'2'},'1':{0:'0',1:'2'},'2':{0:'0',1:'1'}}
        mod = pow(10,9)+7

        for i in range(n):
            for j in range(3**m):
                s = ternary(j)
                s = '0'*(m-len(s))+s
                fl = 1
                for k in range(1,m):
                    if s[k] == s[k-1]:
                        fl = 0
                        break
                if fl:
                    if i == 0:
                        dp[i][j] += 1
                    else:
                        for k in range(2**m):
                            t = ''
                            for x in range(m):
                                t += mapping[s[x]][((k&(1<<x))>0)]
                            dp[i][j] += dp[i-1][int(t,3)]
                            dp[i][j] %= mod
                    
                ans += (i == n-1)*dp[i][j]
                ans %= mod
                
        return ans
                    
20200