Make DAG of adjacent rows
\nM = 10 ** 9 + 7\n\ncache = {}\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        if m not in cache:\n            good = []\n     
```\nM = 10 ** 9 + 7\n\ncache = {}\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        if m not in cache:\n            good = []\n            def gen(arr):\n                if len(arr) == m:\n                    good.append(arr[:])\n                    return\n                for l in range(3):\n                    if arr and l == arr[-1]:\n                        continue\n                    arr.append(l)\n                    gen(arr)\n                    arr.pop()\n            gen([])\n            edges = [[] for _ in range(len(good))]\n            g = len(good)\n            for i in range(g):\n                for j in range(g):\n                    valid = True\n                    for k in range(m):\n                        if good[i][k] == good[j][k]:\n                            valid = False\n                            break\n                    if valid:\n                        edges[i].append(j)\n            cache[m] = edges\n        edges = cache[m]\n        g = len(edges)\n        dp = [1] * g\n        ndp = [0] * g\n        for _ in range(1, n):\n            for i in range(g):\n                ndp[i] = 0\n                for j in edges[i]:\n                    ndp[i] += dp[j]\n                    ndp[i] %= M\n            dp, ndp = ndp, dp\n        return sum(dp) % M\n```
['Python']