Simple DP Implementation
\nclass Solution(object):\n    def colorTheGrid(self, m, n):\n        """\n        :type m: int\n        :type n: int\n        :rtype: int\n        """\n       
```\nclass Solution(object):\n    def colorTheGrid(self, m, n):\n        """\n        :type m: int\n        :type n: int\n        :rtype: int\n        """\n        # m = 2\n\n        patterns = ["a", "b", "c"]\n        for i in range(m-1):\n            new_patterns = []\n            for p in patterns:\n                for color in ["a","b","c"]:\n                    if color != p[-1]:\n                        new_patterns.append(p + color)\n            patterns = new_patterns\n        \n        \n        nxt_patterns = collections.defaultdict(list)\n        for i in range(len(patterns)):\n            for j in range(i+1, len(patterns)):\n                p1 = patterns[i]\n                p2 = patterns[j]\n                if all(p1[k] != p2[k] for k in range(len(p1))):\n\n                    nxt_patterns[p1].append(p2)\n                    nxt_patterns[p2].append(p1)\n                    \n        curcols = collections.defaultdict(int)\n        for p in patterns:\n            curcols[p] += 1\n        for j in range(1, n):\n            nxtcols = collections.defaultdict(int)\n            for col in curcols:\n                for nxtcol in nxt_patterns[col]:\n                    nxtcols[nxtcol] += curcols[col]\n            curcols = nxtcols\n        return sum(curcols.values()) % (10**9+7)\n                \n```
['Dynamic Programming']