Python recursive DP, abstracted as a Graph counting problem
 # Intuition  \n\n\n\n\n\n# Complexity\nLet w := 3^m,\n- Time complexity: O(w^2m+w^2n)\n\n\n- Space complexity: O(w^2+wn)\n\n\n# Code\n\nM = 1_000_000_007\n\n\n
<!-- # Intuition -->\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n<!-- # Approach -->\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\nLet $$w := 3^m$$,\n- Time complexity: $$O(w^2m+w^2n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(w^2+wn)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nM = 1_000_000_007\n\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        W = [x for x in product(range(3), repeat=m) if all(map(ne, x, x[1:]))]\n        if n == 1:\n            return len(W)\n        adj = [[i for i, y in enumerate(W) if all(map(ne, x, y))] for x in W]\n\n        @cache\n        def dp(i, j):\n            if j == n:\n                return len(adj[i])\n            return sum(dp(k, j+1) for k in adj[i]) % M\n\n        return sum(dp(i, 2) for i in range(len(W))) % M\n```
['Dynamic Programming', 'Graph', 'Python3']