Easy DP Approach using UnorderedMap
\n#define ll long long int\nconst int mod=1e9+7;\nclass Solution {\n    int r,c;\n    string curr;\n    vector<string> comb; // all possible valid combinations 
```\n#define ll long long int\nconst int mod=1e9+7;\nclass Solution {\n    int r,c;\n    string curr;\n    vector<string> comb; // all possible valid combinations to color a column\n    unordered_map<string,ll> dp[1003];\npublic:\n\t// finds all possible color combinations to color a given column\n    void findCombinations(vector<int>& col){\n        \n        if(curr.length()==r){\n            for(int i=r-1;i>0;i--){\n                if(curr[i]==curr[i-1])\n                    return;\n            }\n            comb.push_back(curr);\n\t\t\treturn;\n        }\n \n        for(int i=0;i<3;i++){\n            curr=curr+to_string(col[i]);\n            findCombinations(col);\n            curr.pop_back();\n        }\n    }\n    \n\t// checks if ith coloumn can be colored as s and i+1th col can be colored as t\n    bool check(string s,string t){\n        for(int i=0;i<r;i++){\n            if(s[i]==t[i])\n                return 0;\n        }\n        return 1;\n    }\n\n    int colorTheGrid(int m, int n) {\n        vector<int> col={1,2,3};\n        r=m;\n        c=n;\n        curr="";\n\t\t\n\t\t// finds all valid combinations\n        findCombinations(col);\n        \n        for(auto s:comb)\n            dp[n-1][s]=1;\n        \n\t\t// checks all combinations which can be used to color 2 consecutive columns\n        vector<int> list[comb.size()+10];\n        for(int i=0;i<comb.size();i++)\n            for(int j=i;j<comb.size();j++){\n                if(check(comb[i],comb[j])){\n                    list[i].push_back(j);\n                    list[j].push_back(i);\n                }\n            }\n        \n        for(int i=n-2;i>=0;i--)\n            for(int j=0;j<comb.size();j++){\n                ll nxt=0;\n                for(auto ind:list[j])\n                    nxt=(nxt+dp[i+1][comb[ind]])%mod;\n                dp[i][comb[j]]=nxt;\n            }\n        \n        ll ans=0;\n        for(auto e:dp[0])\n            ans=(ans+e.second)%mod;\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']