Mutation from hiepit's 3 X N solution
I know this solution looks a bit silly but understandable and feasible!\nMutate from : https://leetcode.com/problems/painting-a-grid-with-three-different-colors
I know this solution looks a bit silly but understandable and feasible!\nMutate from : https://leetcode.com/problems/painting-a-grid-with-three-different-colors/discuss/1330185/C%2B%2BPython-DP-and-DFS-and-Bitmask-Picture-explain-Clean-and-Concise\n```\nclass Solution {\n    int dp[1001][4][4][4][4][4] = {};\npublic:\n    int colorTheGrid(int m, int n) {\n        vector<int> colors = {1,2,3};\n        return dfs(n,0,0,0,0,0,colors,m);\n    }\n    int dfs(int n, int a0, int b0, int c0,int d0,int e0, const vector<int> &colors,int &m){\n        if(n == 0) return 1;\n        if(dp[n][a0][b0][c0][d0][e0] > 0) return dp[n][a0][b0][c0][d0][e0];\n        int res = 0;\n        for(int a : colors){\n            if(a == a0) continue;\n            if(m==1) {res += dfs(n-1,a,0,0,0,0,colors,m);res %= 1000000007;}\n            else{\n                for(int b : colors){\n                    if(b == a || b == b0) continue;\n                    if(m==2) {res += dfs(n-1,a,b,0,0,0,colors,m); res %= 1000000007;}\n                    else{\n                        for(int c : colors){\n                            if(c == b || c == c0) continue;\n                            if(m==3) {res += dfs(n-1,a,b,c,0,0,colors,m); res %= 1000000007;}\n                            else{\n                                for(int d : colors){\n                                    if(d == c || d == d0) continue;\n                                    if(m==4) {res += dfs(n-1,a,b,c,d,0,colors,m);res %= 1000000007;}\n                                    else{\n                                        for(int e : colors){\n                                            if(e == d || e == e0) continue;\n                                            res+= dfs(n-1,a,b,c,d,e,colors,m);res %= 1000000007;\n                                        }\n                                    }\n                                }\n                            }\n                        }\n                    }\n                }\n            }\n        }\n        return dp[n][a0][b0][c0][d0][e0] = res;\n    }\n};\n```
[]