My C++ Solution... with dfs and bottom up dp
\nclass Solution {\npublic:\n    vector<string> stripes;\n    vector<char> temp;\n    int p = 1e9 + 7;\n    int colorTheGrid(int m, int n) {\n        // we want
```\nclass Solution {\npublic:\n    vector<string> stripes;\n    vector<char> temp;\n    int p = 1e9 + 7;\n    int colorTheGrid(int m, int n) {\n        // we want to know what are the different\n        // ways a single row can be filled with\n        // given that the total number of columns\n        // are m and we have three available colors\n        dfs(m, \' \', 0);\n        // now we have all the available stripes to fill a row with\n        int z = stripes.size();\n        vector<vector<int>> adj(z);\n        for(int i = 0; i < z; i++)\n        for(int j = i + 1; j < z; j++)\n            if(!conflict(i, j)) {\n                adj[i].push_back(j);\n                adj[j].push_back(i);\n            }\n        // dp[i][j] tells us the different ways we can\n        // colors m * (i + 1) table such that the last\n        // stripe is stripes[j]\n        vector<vector<int>> dp(n, vector<int>(z));\n        for(int i = 0; i < n; i++)\n        for(int j = 0; j < z; j++)\n            if(i == 0) dp[i][j] = 1;\n            else for(int nbr : adj[j])\n                dp[i][j] = (dp[i][j] + dp[i - 1][nbr]) % p;\n        int total = 0;\n        for(int j = 0; j < z; j++)\n            total = (total + dp[n - 1][j]) % p;\n        return total;\n    }\n    bool conflict(int i, int j) {\n        string a = stripes[i], b = stripes[j];\n        for(int i = 0; i < a.size(); i++)\n            if(a[i] == b[i]) return true;\n        return false;\n    }\n    void dfs(int m, char last, int j) {\n        if(j == m) {\n            string s = "";\n            for(char c : temp) s += c;\n            stripes.push_back(s);\n        } else {\n            if(last != \'r\') {\n                temp.push_back(\'r\');\n                dfs(m, \'r\', j + 1);\n                temp.pop_back();\n            }\n            if(last != \'b\') {\n                temp.push_back(\'b\');\n                dfs(m, \'b\', j + 1);\n                temp.pop_back();\n            }\n            if(last != \'g\') {\n                temp.push_back(\'g\');\n                dfs(m, \'g\', j + 1);\n                temp.pop_back();\n            }\n        }\n    }\n};\n```
[]