Java Dp
\nclass Solution {\n    public void trav(int m,List<String>list,String s)\n    {\n        int len=s.length();\n        if(len>1 && s.charAt(len-1)==s.charAt(len
```\nclass Solution {\n    public void trav(int m,List<String>list,String s)\n    {\n        int len=s.length();\n        if(len>1 && s.charAt(len-1)==s.charAt(len-2))\n            return;\n        if(m==0)\n        {\n            list.add(s);\n            return;\n        }\n        trav(m-1,list,s+"r");\n        trav(m-1,list,s+"g");\n        trav(m-1,list,s+"b");\n        return;\n    }\n    public int comp(String s,String t)\n    {\n        for(int i=0;i<s.length();i++)\n        {\n            if(s.charAt(i)==t.charAt(i))\n                return 0;\n        }\n        return 1;\n    }\n    public int colorTheGrid(int m, int n) {\n        List<String>list=new ArrayList<>();\n        trav(m,list,"");\n        int mod=1000000007,s=list.size();\n        int arr[][]=new int[s][s];\n        for(int i=0;i<s;i++)\n        {\n            for(int j=0;j<s;j++)\n            {\n                arr[i][j]=comp(list.get(i),list.get(j));\n            }\n        }\n        int dp[]=new int[s];\n        for(int i=0;i<s;i++)\n            dp[i]=1;\n        for(int i=2;i<=n;i++)\n        {\n            int pres[]=new int[s];\n            for(int j=0;j<s;j++)\n            {\n                for(int k=0;k<s;k++)\n                {\n                    if(arr[j][k]==1)\n                        pres[j]=(pres[j]%mod+dp[k]%mod)%mod;\n                }\n            }\n            dp=pres;\n        }\n        int ans=0;\n        for(int i=0;i<s;i++)\n            ans=(ans%mod+dp[i]%mod)%mod;\n        return ans;\n    }\n}\n```
[]