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

#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define MOD 1000000007
class Solution {
   private:
    // r=0,g=1,y=2;
    vector<vector<int>> singleRowCombos = {
        {0, 1, 0},
        {0, 1, 2},
        {0, 2, 1},
        {0, 2, 0},
        {1, 0, 1},
        {1, 0, 2},
        {1, 2, 0},
        {1, 2, 1},
        {2, 0, 2},
        {2, 0, 1},
        {2, 1, 0},
        {2, 1, 2}};

    
    bool isValid(vector<int>& curr, vector<int>& prev) {
        for (int i = 0; i < 3; i++) {
            if (curr[i] == prev[i])
                return 0;
        }
        return 1;
    }

    int helper(int rowIdx, int n, vector<int>& prev, vector<vvvi>& dpArr) {
        int ans = 0;
        
        if (rowIdx == n)
            return 1;
        if (dpArr[rowIdx][prev[0]][prev[1]][prev[2]] != -1) return dpArr[rowIdx][prev[0]][prev[1]][prev[2]] % MOD;
        for (vector<int>& combo : singleRowCombos) {
            if (isValid(combo, prev))
                ans = ((ans % MOD) + (helper(rowIdx + 1, n, combo, dpArr) % MOD)) % MOD;
        }
        return (dpArr[rowIdx][prev[0]][prev[1]][prev[2]] = (ans % MOD));
    }

   public:
    int numOfWays(int n) {
        if (n == 1)
            return (int)singleRowCombos.size();
        vector<vvvi> dpArr(n + 1, vvvi(4, vvi(4, vi(4, -1))));
        vector<int> prev = {3, 3, 3};
        return helper(0, n, prev, dpArr);
    }
};
60605