Python3. DFS (top down dp) without bit masking
\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        column_patterns = []\n        \n\t\t# collect all column patterns with using back
```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        column_patterns = []\n        \n\t\t# collect all column patterns with using backtracking\n        def backtrack(pattern):\n            if len(pattern) == m:\n                column_patterns.append(pattern)\n            else:\n                for i in range(3):\n                    if not pattern or i != pattern[-1]:\n                        backtrack(pattern + [i])\n\n        backtrack([])\n\n\t\t# for each column pattern find all compatible ones\n        compatible_patterns = [[] for _ in column_patterns]\n        for i in range(len(column_patterns)):\n            for j in range(i + 1, len(column_patterns)):\n                for k in range(m):\n                    if column_patterns[i][k] == column_patterns[j][k]:\n                        break\n                else:\n                    compatible_patterns[i].append(j)\n                    compatible_patterns[j].append(i)\n\n        compatible_patterns.append(list(range(len(column_patterns)))) # pseudo column that compatible with all to start dfs\n        mod = 10 ** 9 + 7\n\n\t\t# straightforward dp\n        @cache\n        def dfs(i, n):\n            if n == 0:\n                return 1\n            count = 0\n            for j in compatible_patterns[i]:\n                count = (count + dfs(j, n - 1)) % mod\n            return count\n        return dfs(-1, n)\n        \n```
[]