Python 3 dp
python\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        endings = set()\n        \n        def dfs_ending(i, cur_ending):\n        
```python\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        endings = set()\n        \n        def dfs_ending(i, cur_ending):\n            if i == m:\n                endings.add(cur_ending)\n                return\n            for to_add in range(3):\n                c = str(to_add)\n                if cur_ending and cur_ending[-1] == c:\n                    continue\n                dfs_ending(i + 1, cur_ending + c)\n        dfs_ending(0, \'\')\n        MOD = 10 ** 9 + 7\n        dp = [defaultdict(int) for _ in range(2)]\n        for ending in endings:\n            dp[1][ending] = 1\n            \n        def compatible(e1, e2):\n            for i in range(len(e1)):\n                if e1[i] == e2[i]:\n                    return False\n            return True\n        \n        for i in range(2, n + 1):\n            dp[i % 2] = defaultdict(int)\n            for prev_ending, prev_count in dp[(i-1) % 2].items():\n                for ending in endings:\n                    if compatible(prev_ending, ending):\n                        dp[i % 2][ending] += prev_count\n                        dp[i % 2][ending] %= MOD\n        res = 0\n        for v in dp[n % 2].values():\n            res += v\n            res %= MOD\n        return res\n```
[]