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

import numpy as np

class Solution:
    def numOfWays(self, n: int) -> int:
        # n x 3 grid, paint with one of RYG
        # no horizontal or vertical neighbor may share a color

        # lets rename colors abc
        # and further declare that the left-most color on the prior row is a
        # and second is b

        # patterns:
        #    aba          abc         # that's it!

        #    if prior is aba:           prior abc
        #
        # aba
        # abc
        # aca
        # acb
        # bab ##                aba        ##
        # bac ##                abc
        # bca                   abc        ##
        # bcb ##                aba        ##
        # cab ##                abc        ##
        # cac ##                aba
        # cba
        # cbc
        
        # so if, through row r-1 we have 
        #    n_aba ways to get type aba
        #    n_abc ways to get type abc
        #
        # then the updated number of ways is
        #      n_aba, n_abc = 2*n_abc + 3*n_aba, 2*n_abc + 2*n_aba
        #
        # because
        #     we can append 3 aba type rows to aba, 2 abc type to aba
        #     we an append 2 aba and 2 abc type rows to abc
        #     (we get this by counting the number of ways
        #      to append aba-type or abc-type above in terms
        #      the number of aba and abc types of the prior row)

        # and the update is linear and Markov so we get

        if n == 1: return 12

        n -= 1
        p = np.array([[3,2],[2,2]], dtype=np.int64)
        Tn = np.eye(2, dtype=np.int64)
        BIG = 10**9+7
        while n:
            if n & 1:
                Tn = Tn.dot(p)

            Tn %= BIG
            p = p.dot(p)
            p %= BIG

            n >>= 1

        # there are 12 total, of which 3 perm 2 = 6 of which are of the form aba
        # so we get Tn * [6; 6] == 6*sum of row for both rows
        # and the total ways is the sum of those, so 6*sum of matrix
        return (6*np.sum(Tn)) % BIG
28600