You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colors: Red, Yellow, or Green 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).

Given n the number of rows of the grid, return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 109 + 7.

&nbsp;
Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown.


Example 2:

Input: n = 5000
Output: 30228214


&nbsp;
Constraints:


	n == grid.length
	1 &lt;= n &lt;= 5000


class Solution:
    def numOfWays(self, n: int) -> int:
        two_c_options = 6
        tot_options = 12
        for i in range(n-1):
            temp = tot_options
            tot_options = (two_c_options * 5) + ((tot_options - two_c_options) * 4)
            two_c_options = (two_c_options * 3) + ((temp - two_c_options) * 2)
            tot_options = tot_options % (1000000007)
        return tot_options
class Solution {
    int MOD = 1000000007;
    int[][] states = {{0,1,0},{1,0,1},{2,0,1},
                      {0,1,2},{1,0,2},{2,0,2},
                      {0,2,0},{1,2,0},{2,1,0},
                      {0,2,1},{1,2,1},{2,1,2}};
    
    HashMap<Integer, List<Integer>> nextMap = new HashMap<>();
    Long[][] memo;
    
    public int numOfWays(int n) {
        if(n == 0)
            return 0;
        
		// Graph
        for(int prev = 0; prev < 12; prev++){
            List<Integer> nexts = new ArrayList<>();
            for(int next = 0; next < 12; next++){
                if(next == prev) continue;
            
                boolean flag = true;
                for(int i = 0; i < 3; i++){
                    if(states[prev][i] == states[next][i]){
                        flag = false;
                        break;
                    }
                }
                if(flag)
                    nexts.add(next);
            }
            nextMap.put(prev, nexts);
        }
		
		//DFS
        memo = new Long[12][n];
        long ways = 0;
        for(int i = 0; i < 12; i++){
            ways += dfs(i, n-1);
            ways %= MOD;
        }
        
        return (int)(ways);
    }
    
    long dfs(int prev, int n){
        if(n == 0)
            return 1;
        
        if(memo[prev][n] != null)
            return memo[prev][n];
        
        long ways = 0;
        
        List<Integer> nexts = nextMap.get(prev);
        for(int next : nexts){
            ways += dfs(next, n-1);
            ways %= MOD;
        }
        
        memo[prev][n] = ways;
        return ways;
    }
}
class Solution {
public:
    int numOfWays(int n) {
        int mod=1e9+7;
        long long c2=6,c3=6;
        for(int i=2;i<=n;i++){
            long long temp=c3;
            c3=(2*c3+2*c2)%mod;
            c2=(2*temp+3*c2)%mod;
        }
        return (c2+c3)%mod;
    }
};
/**
 * @param {number} n
 * @return {number}
 */
var numOfWays = function(n) {
  const mod = Math.pow(10, 9) + 7;
  const dp212 = [6];
  const dp123 = [6];
  for (let i = 1; i < n; i++) {
    // two sides same
    dp212[i] = (dp212[i - 1] * (5 - 2) + dp123[i - 1] * (6 - 2 - 1 - 1)) % mod;
    // three different colors
    dp123[i] = (dp123[i - 1] * (5 - 1 - 1 - 1) + dp212[i - 1] * (6 - 2 - 2)) % mod;
  }
  return (dp212[n - 1] + dp123[n - 1]) % mod;
};
Number of Ways to Paint N × 3 Grid