DP
Code\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        t = [\'a\', \'b\', \'c\']\n        for i in range(m-1):\n            new = 
# Code\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        t = [\'a\', \'b\', \'c\']\n        for i in range(m-1):\n            new = []\n            for s in t:\n                if s[-1] != \'a\': new.append(s+\'a\')\n                if s[-1] != \'b\': new.append(s+\'b\')\n                if s[-1] != \'c\': new.append(s+\'c\')\n            t = new\n        d = defaultdict(set)\n        for s1, s2 in itertools.combinations(t, 2):\n            for i in range(m):\n                if s1[i] == s2[i]: break\n                if i == m-1: \n                    d[s1].add(s2)\n                    d[s2].add(s1)\n        @cache\n        def dp(s, n):\n            if n == 0: return 1\n            res = 0\n            for ch in d[s]:\n                res += dp(ch, n-1)\n            return res\n        return sum(dp(s, n-1) for s in t)%(10**9+7)\n```
['Python3']