Simple Solution with DP & Bitmask
Use 2bits to represent the state each cell, need 2*m bits since there are m rows\n2. Use 00, 01, 10 to represent 3 types of color\n3.  Update dp[i][j] from dp[i
1. Use 2bits to represent the state each cell, need 2*m bits since there are m rows\n2. Use 00, 01, 10 to represent 3 types of color\n3.  Update dp[i][j] from dp[i-1][k] if j, k, and (j, k) are valid. j, k is the state of the colume\n```\nclass Solution {\npublic:\n    const int M = 1e9+7;\n    int m;\n    \n\t// check if same row has same color\n    bool ok(int x, int y) {\n        for (int i = 0; i < m; i++) {\n            if (((x >> (2*i)) & 3) == (((y >> (2*i)) & 3))) return false;\n        }\n        \n        return true;\n    }\n    \n    bool check(int x) {\n\t\t// check if near row has same color\n        for (int i = 0; i < m - 1; i++) {\n            if (((x >> (2*i)) & 3) == ((x >> (2*(i+1))) & 3)) return false;\n        }\n        \n\t\t// filter state 11 since there are only 3 types of color\n        for (int i = 0; i < m; i++)\n            if (((x >> (2*i)) & 3) == 3) return false;\n        return true;\n    }\n\n    int colorTheGrid(int _m, int n) {\n        m = _m;\n        vector<vector<long long>> dp(2, vector<long long>(1<<(2*m), 0));\n        for(int i = 0; i < 1 << (2*m); i++) {\n            if (check(i))\n                dp[0][i] = 1;\n        }\n        \n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < (1 << (2*m)); j++) {\n                if (check(j)) {\n                    dp[i%2][j] = 0;\n                    for (int k = 0; k < (1 << (2*m)); k++) {\n                        if (check(k) && ok(j, k)) {\n                            dp[i%2][j] = (dp[i%2][j] + dp[(i-1)%2][k]) % M;\n                        }\n                    }\n                }\n            }\n        }\n        \n        long long ans = 0;\n        for (int i = 0; i < 1 << (2*m); i++) {\n            ans = (ans + dp[(n-1)%2][i]) % M;\n        }\n        \n        return ans;\n    }\n};\n```
[]