C++| Brute way | using strings for state
```\nclass Solution {\npublic:\n    void g(string &s,int m,vector&v,int i,string &c){\n        if(i==m){\n            v.push_back(c);\n            return;\n    
```\nclass Solution {\npublic:\n    void g(string &s,int m,vector<string>&v,int i,string &c){\n        if(i==m){\n            v.push_back(c);\n            return;\n        }\n        if(i==0){\n            for(int j=1;j<=3;j++){\n                if(j!=s[i]-\'0\'){\n                    c.push_back(j+\'0\');\n                    g(s,m,v,i+1,c);\n                    c.pop_back();\n                }\n            }\n        }else{\n            for(int j=1;j<=3;j++){\n                if(j!=s[i]-\'0\' && j!=c[i-1]-\'0\'){\n                    c.push_back(j+\'0\');\n                    g(s,m,v,i+1,c);\n                    c.pop_back();\n                }\n            }\n        }\n    }\n    unordered_map<string,int>ma;\n    unordered_map<string,vector<string>>store;\n    int mod = 1e9+7;\n    int f(int n,int m,string s,int i){\n        if(i==n)return 1;\n        string mm = s + "-" + to_string(i);\n        if(ma.count(mm))return ma[mm];\n        string ss="";\n        int ans=0;\n        if(store.count(s)){\n            for(auto x:store[s]){ \n                ans = (ans%mod + f(n,m,x,i+1)%mod)%mod;\n            }\n        }\n        else{\n            vector<string> v;\n            g(s,m,v,0,ss);\n            store[s] = v;\n            for(auto x:v){ \n                ans = (ans%mod + f(n,m,x,i+1)%mod)%mod;\n            }\n        }\n        return ma[mm] = ans;\n    }\n    int colorTheGrid(int m, int n) {\n        string s = "";\n        for(int i=0;i<m;i++)s.push_back(\'0\');\n        return f(n,m,s,0);\n    }\n};
[]