DP on Counter() base (without recursion) (60% | 81%)
Code\n\nclass Solution:\n    \n    def colorTheGrid(self, m: int, n: int) -> int:\n        mod = 10 ** 9 + 7\n\n        def get_first_line(m) -> list[str]:\n   
# Code\n```\nclass Solution:\n    \n    def colorTheGrid(self, m: int, n: int) -> int:\n        mod = 10 ** 9 + 7\n\n        def get_first_line(m) -> list[str]:\n            """Returns all possible (24) variations of the first line.\n            """\n            res = [[], [""]]\n            for i in range(m):\n                for r in res[(1-i) % 2]:\n                    for c in \'rgb\':\n                        if not r or r[-1] != c:\n                            res[i % 2].append(r + c)\n                res[(1-i) % 2].clear()\n            return res[i % 2]\n\n        \n        @cache\n        def get_lines(prev_line: str) -> tuple[str]:\n            """Returns all possible variations of the\n               next line based on the previous one.\n            """\n            return tuple(filter(\n                lambda el: not set(enumerate(prev_line)) & set(enumerate(el)),\n                first_line\n            ))\n\n        prev_counter = Counter(first_line := get_first_line(m))\n        \n        # find and count options for the following lines\n        for _ in range(n - 1):\n            cur_counter = Counter()\n            for prev_line, cnt in prev_counter.items():\n                cur_counter.update(\n                    {key: cnt % mod for key in get_lines(prev_line)}\n                )\n            prev_counter = cur_counter\n\n        return sum(prev_counter.values()) % mod\n```
['Python3']