[Python3] top-down dp
\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        \n        @cache\n        def fn(i, j, mask): \n            """Return number of
\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        \n        @cache\n        def fn(i, j, mask): \n            """Return number of ways to color grid."""\n            if j == n: return 1 \n            if i == m: return fn(0, j+1, mask)\n            ans = 0 \n            for x in 1<<2*i, 1<<2*i+1, 0b11<<2*i: \n                mask0 = mask ^ x\n                if mask0 & 0b11<<2*i and (i == 0 or (mask0 >> 2*i) & 0b11 != (mask0 >> 2*i-2) & 0b11): \n                    ans += fn(i+1, j, mask0)\n            return ans % 1_000_000_007\n        \n        return fn(0, 0, 0)\n```
['Python3']