1411. Number of Ways to Paint N × 3 Grid

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.

class Solution {
public:
    int numOfWays(int n) {
        long long two = 6, three = 6, ntwo, nthree, mod = 1e9 + 7;
        while(--n) {
            ntwo = (two * 3 + three * 2) % mod;
            nthree = (three * 2 + two * 2) % mod;
            two = ntwo;
            three = nthree;
        }
        return (two + three) % mod;
    }
};