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

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: m = 1, n = 1
Output: 3
Explanation: The three possible colorings are shown in the image above.


Example 2:

Input: m = 1, n = 2
Output: 6
Explanation: The six possible colorings are shown in the image above.


Example 3:

Input: m = 5, n = 5
Output: 580986


&nbsp;
Constraints:


	1 &lt;= m &lt;= 5
	1 &lt;= n &lt;= 1000


class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        from functools import reduce
        MOD = 10**9 + 7
        sum_mod = lambda x,y: (x+y)%MOD
        
        def normalize(pat_var):
            mapping = { e:i+1 for i, e in enumerate(pat_var[0:2]) }
            mapping[list({1,2,3}.difference(mapping.keys()))[0]] = 3
            return tuple([ mapping[e] for e in pat_var])
        
        def get_pats(m, i, pat, pats):
            if i == m-1:
                pats.append(tuple(pat))
                return
            i_nx = i+1
            for p_it_nx in (1,2,3):
                if (i_nx <= 1 and p_it_nx == i_nx+1 ) or (i_nx >= 2 and p_it_nx != pat[-1]):
                    pat.append(p_it_nx)
                    get_pats(m, i_nx, pat, pats)
                    pat.pop()
            return pats
        
        def get_trans(pat, i, pat_pre, trans):
            if i == len(pat)-1:
                pat_nl = normalize(pat_pre)
                trans[pat_nl] = trans.get(pat_nl, 0) + 1
                return
            for p_it_pre in (1,2,3):
                i_nx = i+1
                if (p_it_pre != pat[i_nx]
                    and (not pat_pre or p_it_pre != pat_pre[-1])):
                    pat_pre.append(p_it_pre)
                    get_trans(pat, i_nx, pat_pre, trans)
                    pat_pre.pop()
            return trans

        pats = get_pats(m, -1, [], [])
        # {pattern_i: {pattern_pre:count}}
        pat_trans = { pat: get_trans(pat, -1, [], {}) for pat in pats }  
        
        p_counts = { pat:1 for pat in pat_trans.keys() }
        for i in range(n-1):
            p_counts_new = {}
            for pat, trans in pat_trans.items():
                p_counts_new[pat] = reduce(sum_mod, (p_counts[pat_pre] * cnt for pat_pre, cnt in trans.items()))
            p_counts = p_counts_new
        
        res = reduce(sum_mod, (cnt for cnt in p_counts.values()))
        perms = reduce(lambda x,y: x*y, (3-i for i in range(min(3,m))))
        return (res * perms) % MOD
class Solution 
{
    static int mod=(int)(1e9+7);
   public static int dfs(int n,ArrayList<ArrayList<Integer>> arr,int src,int dp[][])
   {
       if(n==0)
       {
           return 1;
       }
       if(dp[n][src]!=-1)
       {
           return dp[n][src];
       }
       int val=0;
    for(Integer ap:arr.get(src))
    {
         val=(val%mod+dfs(n-1,arr,ap,dp)%mod)%mod;
    }
       return dp[n][src]=val;
   }
   public static void val(ArrayList<String> arr,int color,int m,String s)
    {
        if(m==0)
        {
            arr.add(s);
            return;
        }
       for(int i=0;i<3;i++)
       {
           if(color!=i)
           val(arr,i,m-1,s+i);
       }
    }
    public static boolean Match(String s,String s1)
    {
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)==s1.charAt(i))
            {
                return false;
            }
        }
        return true;
    }
    public int colorTheGrid(int m, int n)
    {
        ArrayList<String> arr=new ArrayList<String>();
        for(int i=0;i<3;i++)
        {
            String s="";
            val(arr,i,m-1,s+i);
        }
        ArrayList<ArrayList<Integer>> adj=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<arr.size();i++)
        {
            adj.add(new ArrayList<Integer>());
        }
    
        for(int i=0;i<adj.size();i++)
        {
            for(int j=0;j<arr.size();j++)
            {
                if(Match(arr.get(i),arr.get(j)))
                {
                    adj.get(i).add(j);
                }
            }
        }
  int dp[][]=new int[n+1][adj.size()+1];
        for(int i=0;i<=n;i++)
        {
            Arrays.fill(dp[i],-1);
        }
        int sum12=0;
        for(int i=0;i<arr.size();i++)
        {
                 sum12=(sum12%mod+dfs(n-1,adj,i,dp)%mod)%mod;
        }
        return sum12;
       
    }
}
vector<string> moves;
int MOD = 1e9 + 7;
void fill(string s, int n, int p){
    if(n==0){
        moves.push_back(s);
        return;
    }
    for(int i=1; i<4; i++){
        if(p==i){
            continue;
        }
        string m = to_string(i);
        fill(s+m, n-1, i);
    }
    return;
}
class Solution {
public:
    vector<vector<int>>memo;
    int solve(int n, int lastIdx, int m){
        if (n == 0) return 1;
        int ret = 0;
        if (memo[n][lastIdx] != -1) return memo[n][lastIdx];
        string last = moves[lastIdx];
        for (int idx = 0; idx<moves.size(); idx++) {
            string move = moves[idx];
            bool same = false;
            for (int i = 0; i < m; i++) if (move[i] == last[i]) same = true;   
            if (!same) ret = (ret + solve(n - 1, idx, m)%MOD)%MOD;
        }
        return memo[n][lastIdx]= ret%MOD;
    }
    int colorTheGrid(int m, int n){
        moves.clear();
        fill("", m, -1);
        //cout<<moves.size()<<endl;
        memo.resize(n + 1, vector<int>(moves.size(), -1));
        int ret = 0;
        for (int idx = 0; idx < moves.size(); idx++)
            ret =  (ret + solve(n-1, idx, m)%MOD)%MOD;
        return ret;
    }
};
// transform any decimal number to its ternary representation
let ternary=(num,len)=>{
    let A=[],times=0
    while(times++<len)
        A.push(num%3),num= (num-num%3)/3
    return A
}
// deduce whether my array does not contain 2 consecutive elements
let adjdiff=Array=>Array.every((d,i)=>i==0||d!==Array[i-1])
//main
var colorTheGrid = function(n, m) {
    let mod=1e9+7,adj=[...Array(3**(n))].map(d=>new Set()),
    //1.turn every potential state to a ternary(base3) representation
        base3=[...Array(3**n)].map((d,i)=>ternary(i,n)),
		//3 conditions such that state a can be previous to state b 
        ok=(a,b)=>adjdiff(base3[a])&& adjdiff(base3[b])&& base3[a].every( (d,i)=>d!==base3[b][i])
    //2.determine what are the acceptable adjacent states of any given state
    for(let m1=0;m1<3**n;m1++)
        for(let m2=0;m2<3**n;m2++)
            if(ok(m1,m2))
                adj[m1].add(m2),adj[m2].add(m1)
    //3.do 2-row dp, where dp[state]= the number of colorings where the last line is colored based on state
    let dp=[...Array(3**n)].map((d,i)=>Number(adjdiff(base3[i])))
    for(let i=1,dp2=[...Array(3**n)].map(d=>0);i<m;i++,dp=[...dp2],dp2.fill(0))
        for(let m1=0;m1<3**n;m1++)
            for(let prev of Array.from(adj[m1]))
                dp2[m1]=(dp2[m1]+dp[prev])%mod
    return dp.reduce((a,c)=> (a+c) %mod ,0)
};
Painting a Grid With Three Different Colors