[Python 3] Bitmask DP
Intuition\nsince m is very small so it seems sensible to use Bitmask DP here\n\n# Approach\nwe use first 5 bits for red, next 5 for blue and next 5 bits for gre
# Intuition\nsince m is very small so it seems sensible to use Bitmask DP here\n\n# Approach\nwe use first 5 bits for red, next 5 for blue and next 5 bits for green\nand continously check for each position if we can use a specific color.\n\n# Time Compexity:\nO(n\\*m\\*2^(2\\*m))\n\n# Code\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        colors=[0,5,10]\n        def next(prev,curr,j):\n            A=[]\n            for color in colors:\n                if prev&(1<<(j+color))==0 and (j==0 or curr&(1<<(j+color-1))==0):\n                    A.append(curr|1<<(j+color))\n            return A\n\n        mod=10**9+7\n        @cache\n        def solve(prev,curr,i,j):\n            if i==n:\n                return 1\n            if j==m:return solve(curr,0,i+1,0)\n            new=next(prev,curr,j)\n            res=0\n            if new:\n                for final in new:\n                    res+=solve(prev,final,i,j+1)\n            return res%mod\n        return solve(0,0,0,0)              \n        \n```
['Python3']