dp + bitmask | brute-force dp
\nclass Solution {\npublic:\n    int n,m,dp[1000][5][(1<<10)],mod=1e9+7;\n    \n    int sol(int i,int j,int mask)\n    {\n        if(i==n) return 1;\n        if
```\nclass Solution {\npublic:\n    int n,m,dp[1000][5][(1<<10)],mod=1e9+7;\n    \n    int sol(int i,int j,int mask)\n    {\n        if(i==n) return 1;\n        if(j==m) return sol(i+1,0,mask);\n        \n        long ans=dp[i][j][mask];\n        if(ans!=-1) return ans;\n        ans=0;\n        \n        for(int k=1;k<=3;k++)\n        {\n            int t=((1<<10)-1) ^ (3<<2*j);   // 11 11 00(jth 00) 11 11\n            int nwmask=(mask & t) ^ (k<<2*j);   // change mask = 01 10 00(jth 00) 11 10  ^  00 00 k 00 00  \n            \n            int up=(mask>>(2*j))%4; // mask\'s jth value in (i-1)\'s row\n            int lst=0;\n            if(j) lst=(mask>>(2*(j-1)))%4;  //  mask\'s (j-1)th value i ith row; \n            \n            if(k==up || k==lst) continue;\n            ans+=sol(i,j+1,nwmask);\n        }\n        ans%=mod;\n        return dp[i][j][mask]=ans;\n    }\n    \n    int colorTheGrid(int mm, int nn) \n    {\n        n=nn; m=mm;\n        memset(dp,-1,sizeof(dp));\n        return sol(0,0,0);\n    }\n};\n```
['Dynamic Programming', 'C', 'Bitmask', 'C++']