[Python] Straight forward solution
Using dp. Consider each row to be a state, we can find the valid adjacent states. Becomes number of paths problem.\nTime complexity : O(n*3^m) \n```\n\nfrom fun
Using dp. Consider each row to be a state, we can find the valid adjacent states. Becomes number of paths problem.\nTime complexity : O(n*3^m) \n```\n\nfrom functools import cache, lru_cache\nfrom itertools import product\n\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        mod = 10 ** 9 + 7\n\n        def check(pos):\n            return all(a != b for a, b in zip(pos, pos[1:]))\n\n        def neighs(pos1, pos2):\n            return all(a != b for a, b in zip(pos1, pos2))\n\n        states = {\'\'.join(pos) for pos in product(\'RGB\', repeat=m) if check(pos)}\n        adj = {}\n        for state in states:\n            adj[state] = [next_state for next_state in states if neighs(state, next_state)]\n\n        @cache\n        def f(prv_state, N):\n            if N == 0:\n                return 1\n            return sum(f(next_state, N - 1) for next_state in adj[prv_state]) % mod\n\n        return sum(f(state, n - 1) for state in states) % mod\n\n\n
['Dynamic Programming', 'Depth-First Search', 'Python']