Simple DP solution✅✅
\n\n# Code\n\nclass Solution {\npublic:\n    int dp[1001][50];\n    int mod=1e9+7;\n    void genrate(int i,string& s,vector<string>& v,char ch,int m){\n        
\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[1001][50];\n    int mod=1e9+7;\n    void genrate(int i,string& s,vector<string>& v,char ch,int m){\n        if(i==m){\n            v.push_back(s);\n            return ;\n        }\n       if(ch!=\'R\'){\n            s+=\'R\';\n            genrate(i+1,s,v,\'R\',m);\n            s.pop_back();\n        }\n        if(ch!=\'G\'){\n            s+=\'G\';\n            genrate(i+1,s,v,\'G\',m);\n             s.pop_back();\n        }\n        if(ch!=\'B\'){\n            s+=\'B\';\n            genrate(i+1,s,v,\'B\',m);\n            s.pop_back();\n        }\n    }\n    int find(int i,vector<string>& v,int pre,int m,int n){\n        if(i==n){\n            return 1;\n        }\n        if(dp[i][pre+1]!=-1){\n            return dp[i][pre+1];\n        }\n        long long ways=0;\n        string last;\n        if(pre!=-1){\n            last=v[pre];\n        }\n        for(int j=0;j<v.size();j++){\n            bool same=false;\n            if(pre!=-1){\n                for(int k=0;k<m;k++){\n                    if(last[k]==v[j][k]){\n                        same=true;\n                        break;\n                    }\n                }\n            }\n                if(!same){\n                    ways=(ways+find(i+1,v,j,m,n))%mod;\n                }\n               \n            \n        }\n        return dp[i][pre+1]=ways;\n    }\n    int colorTheGrid(int m, int n) {\n        memset(dp,-1,sizeof(dp));\n        vector<string> v;\n        string s="";\n        genrate(0,s,v,\'M\',m);\n        return  find(0,v,-1,m,n)%mod;\n    }\n};\n```
['Dynamic Programming', 'C++']