JAVA Intuitive Solution
\nclass Solution {\n    public int colorTheGrid(int m, int n) {\n        Map<String, Integer> map=new HashMap();\n        populateMap(map, m,"");\n        if(n=
```\nclass Solution {\n    public int colorTheGrid(int m, int n) {\n        Map<String, Integer> map=new HashMap();\n        populateMap(map, m,"");\n        if(n==1){\n            return map.size();\n        }\n        Map<String, List<String>> map1=new HashMap();\n        for(String key:map.keySet()){\n            populatePossibleCombinationsInDownRow(key, map1);\n        }\n        int tot=0;\n        if(n==2){\n            for(Map.Entry<String, List<String>> entry: map1.entrySet()){\n                tot=tot+entry.getValue().size();\n            }\n            \n            return tot;\n        }\n            for(Map.Entry<String, List<String>> entry: map1.entrySet()){\n                map.put(entry.getKey(), entry.getValue().size());\n            }\n         Integer mod=1_000_000_007; \n        for(int i=2;i<n;i++){\n          Map<String, Integer> newMap=new HashMap();\n          tot=0;  \n          for(Map.Entry<String, List<String>> entry: map1.entrySet()){\n               int keySum=0;\n                for(String val: entry.getValue()){\n                    keySum=(keySum+map.get(val)%mod)%mod;\n                }\n               newMap.put(entry.getKey(), keySum);\n           tot=(tot+keySum)%mod;  \n          }\n           map=newMap; \n        }\n        return tot;\n    }\n    \n    private void populatePossibleCombinationsInDownRow(String key,  Map<String, List<String>> map){\n       map.put(key, new LinkedList()); \n       populateInnerMap(map, "", key);\n    }\n    \n      private void populateInnerMap( Map<String, List<String>> map, String prefix, String key){\n          if(prefix.equals("")){\n           if(key.charAt(0)==\'r\'){\n               \n              populateInnerMap(map,"g", key);\n              populateInnerMap(map, "b", key);  \n           }else if(key.charAt(0)==\'g\'){\n                 populateInnerMap(map, "r", key);\n                 populateInnerMap(map, "b", key);  \n           }else{\n                 populateInnerMap(map, "r", key);\n                 populateInnerMap(map,"g", key);   \n           }   \n        \n        }else{\n            if(prefix.length()==key.length()){\n                map.get(key).add(prefix);\n                return;\n            }\n            \n            char ls=prefix.charAt(prefix.length()-1);\n            char ch=key.charAt(prefix.length());  \n            if(ls==\'r\'){\n               if(ch==\'b\'){\n                     populateInnerMap(map, prefix+"g", key);                 \n \n               }else if(ch==\'g\'){\n                  populateInnerMap(map, prefix+"b", key);    \n               }else{\n                   populateInnerMap(map, prefix+"g", key);  \n                   populateInnerMap(map, prefix+"b", key);  \n               } \n              \n              \n            }else if(ls==\'g\'){\n               \n                if(ch==\'b\'){\n                     populateInnerMap(map, prefix+"r", key);                 \n \n               }else if(ch==\'r\'){\n                  populateInnerMap(map, prefix+"b", key);    \n               }else{\n                   populateInnerMap(map, prefix+"r", key);  \n                   populateInnerMap(map, prefix+"b", key);  \n               } \n                \n            }else{\n              if(ch==\'r\'){\n                     populateInnerMap(map, prefix+"g", key);                 \n \n               }else if(ch==\'g\'){\n                  populateInnerMap(map, prefix+"r", key);    \n               }else{\n                   populateInnerMap(map, prefix+"r", key);  \n                   populateInnerMap(map, prefix+"g", key);  \n               } \n            }\n        } \n      }\n    \n    private void populateMap( Map<String, Integer> map, int m, String prefix){\n        if(prefix.equals("")){\n          populateMap(map, m, "r");\n          populateMap(map, m, "g");\n          populateMap(map, m, "b");  \n        }else{\n            if(prefix.length()==m){\n                map.put(prefix, 1);\n                return;\n            }\n            \n            char ls=prefix.charAt(prefix.length()-1);\n            if(ls==\'r\'){\n               populateMap(map, m, prefix+"b");\n               populateMap(map, m, prefix+"g");\n            }else if(ls==\'g\'){\n                populateMap(map, m, prefix+"r");\n          populateMap(map, m, prefix+"b");\n            }else{\n                populateMap(map, m, prefix+"r");\n              populateMap(map, m, prefix+"g");\n            }\n        }\n    }\n}\n```
[]