Top-down DP with bit mask
Since m is limited to 5, and colours are limited to 3, we can represent the previous column using a bit mask (two bits for each color). We can have up to 1023 c
Since `m` is limited to `5`, and colours are limited to `3`, we can represent the previous column using a bit mask (two bits for each color). We can have up to 1023 combinations (including white color for convenience) of colors in the column.\n\n1. `cur`: colors for the current column.\n2. `prev`: colors for the previous column.\n3. when we reach the end of the column, we start a new one: `prev = cur`, and `cur = 0`.\n4. for each position, we try each color, providing it\'s not the same as the one on the `left` and `up`.\n\nTo avoid TLE, we need to memoise interim results. For simplicity, we are doing it for the entire row, not for individual cells. So, our memo dimensions are 1000 x 1023 - numbers of columns, and color combinations (bit mask) for the previous column.\n\n**C++**\n```cpp\nint dp[1001][1024] = {};\nint colorTheGrid(int m, int n, int i = 0, int j = 0, int cur = 0, int prev = 0) {\n    if (i == m)\n        return colorTheGrid(m, n, 0, j + 1, 0, cur);\n    if (j == n)\n        return 1;\n    if (i == 0 && dp[j][prev])\n        return dp[j][prev];\n    int res = 0, up = i == 0 ? 0 : (cur >>  ((i - 1) * 2)) & 3, left = prev >> (i * 2) & 3;\n    for (int k = 1; k <= 3; ++k)\n        if (k != left && k != up)\n            res = (res + colorTheGrid(m, n, i + 1, j, cur + (k << (i * 2)), prev)) % 1000000007;\n    if (i == 0)\n        dp[j][prev] = res;\n    return res;\n}\n```
['C']