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

class Solution {
public:
    int numOfWays(int n) {
        using ll = long long;
        const int N = static_cast<int>(pow(3, 3));
        const int M = 1e9 + 7;
        vector<vector<ll>> dp(n, vector<ll> (N));
        auto digits = [&](int x) -> vector<int> {
            vector<int> arr(3);
            int idx = 0;
            while(x) {
                arr[idx++] = (x % 3);
                x /= 3;
            }
            return arr;
        };
        auto check = [&](int cur, int prev) -> bool {
            auto x = digits(cur);
            auto y = digits(prev);
            for(int i = 1; i < 3; i++) {
                if(x[i] == x[i - 1] || y[i] == y[i - 1])
                    return false;
            }
            for(int i = 0; i < 3; i++) {
                if(x[i] == y[i])
                    return false;
            }
            return true;
        };
        // find valid colorings
        set<int> valid;
        for(int i = 0; i < N; i++) {
            auto x = digits(i);
            bool okay = true;
            for(int i = 1; i < 3; i++) {
                okay &= (x[i] != x[i - 1]);
            }
            if(okay) valid.insert(i);
        }
        // find compatible colorings
        set<pair<int, int>> com;
        for(const int &x: valid) {
            for(const int &y: valid) {
                if(check(x, y)) {
                    com.insert({x, y});
                    com.insert({y, x});
                }
            }
        }
        auto add = [&](ll x, ll y) -> ll {
            return (x + y) % M;
        };
        for(int cur = 0; cur < N; cur++) {
            if(valid.count(cur))
                dp[(n - 1) & 1][cur]++;
        }
        for(int i = n - 2; i >= 0; i--) {
            for(int cur = 0; cur < N; cur++) {
                if(!valid.count(cur)) continue;
                dp[i & 1][cur] = 0;
                for(int nxt = 0; nxt < N; nxt++) {
                    if(!valid.count(nxt)) continue;
                    if(com.count({cur, nxt})) {
                        dp[i & 1][cur] = add(dp[i & 1][cur], dp[(i + 1) & 1][nxt]);
                    }
                }
            }
        }
        ll ans = 0;
        for(int cur = 0; cur < N; cur++) {
            ans = add(ans, dp[0][cur]);
        }
        return ans;
    }
};
31085