1931. Painting a Grid With Three Different Colors.cpp
Code\n\nclass Solution {\npublic:\n    int colorTheGrid(int m, int n) {\n        long memo[m][n][1<<2*m]; \n        memset(memo, 0, sizeof(memo));\n        \n  
**Code**\n```\nclass Solution {\npublic:\n    int colorTheGrid(int m, int n) {\n        long memo[m][n][1<<2*m]; \n        memset(memo, 0, sizeof(memo));\n        \n        function<long(int, int, int)> fn = [&](int i, int j, int mask) {\n            if (j == n) return 1l; \n            if (i == m) return fn(0, j+1, mask); \n            if (!memo[i][j][mask]) \n                for (const int& x : {1<<(2*i), 1<<(2*i+1), 3<<(2*i)}) {\n                    int mask0 = mask ^ x; \n                    if ((mask0 & 3<<2*i) != 0 && (i == 0 || (mask0>>2*i & 3) != (mask0>>2*i-2 & 3))) {\n                        memo[i][j][mask] = (memo[i][j][mask] + fn(i+1, j, mask0)) % 1\'000\'000\'007; \n                    }\n                }\n            return memo[i][j][mask]; \n        };\n        \n        return fn(0, 0, 0); \n    }\n};\n```
['C']