easy with all steps
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\n- Time 
# 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\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution\n{\npublic:\n    int dp[1001][1 << 10];\n    int mod=1000000007;\n    int solve(int row, int col, int preMask, int curMask, int n, int m)\n    {\n        if (col == m)\n        {\n            return 1;\n        }\n        if (dp[col][preMask] != -1)\n        {\n            return dp[col][preMask];\n        }\n        if (row == n)\n        {\n            return solve(0, col + 1, curMask, 0, n, m)%mod;\n        }\n        long long ans = 0;\n        for (int k = 1; k <= 3; k++)\n        {\n            int colorAtPrevCol = 0;\n            if ((1 << (2 * row)) & preMask)\n            {\n                colorAtPrevCol = colorAtPrevCol | (1 << 0);\n            }\n            if ((1 << (2 * row + 1)) & preMask)\n            {\n                colorAtPrevCol = colorAtPrevCol | (1 << 1);\n            }\n           \n\n            int colorAtSameCol = 0;\n            if (row > 0)\n            {\n                if ((1 << (2 * row - 2)) & curMask)\n                {\n                    colorAtSameCol |= (1 << 0);\n                }\n                if ((1 << (2 * row - 1)) & curMask)\n                {\n                    colorAtSameCol |= (1 << 1);\n                }\n                if (colorAtPrevCol != k && colorAtSameCol != k)\n                {\n                    if (k == 1)\n                    {\n\n                        ans = (ans + solve(row + 1, col, preMask, curMask | (1 << (2 * row)), n, m))%mod;\n                    }\n                    else if (k == 2)\n                    {\n                        ans = (ans + solve(row + 1, col, preMask, curMask | (1 << (2 * row + 1)), n, m))%mod;\n                    }\n                    else\n                    {\n                        ans = (ans + solve(row + 1, col, preMask, (curMask | (1 << (2 * row)) | (1 << (2 * row + 1))), n, m))%mod;\n                    }\n                }\n            }\n            else\n            {\n                if (colorAtPrevCol != k)\n                {\n                    if (k == 1)\n                    {\n\n                        ans = (ans + solve(row + 1, col, preMask, curMask | (1 << (2 * row)), n, m))%mod;\n                    }\n                    else if (k == 2)\n                    {\n                        ans = (ans + solve(row + 1, col, preMask, curMask | (1 << (2 * row + 1)), n, m))%mod;\n                    }\n                    else\n                    {\n                        ans = (ans + solve(row + 1, col, preMask, (curMask | (1 << (2 * row)) | (1 << (2 * row + 1))), n, m))%mod;\n                    }\n                }\n            }\n        }\n\n        if (row == 0)\n        {\n            dp[col][preMask] = ans%mod;\n        }\n        return ans%mod;\n    }\n    int colorTheGrid(int m, int n)\n    {\n        memset(dp, -1, sizeof(dp));\n        return solve(0, 0, 0, 0, m, n);\n    }\n};\n```
['C++']