Same as N*3 colors c++ best easy soln
```\n//just do n*3 and generalise case for 1,2,3,4,5 copy \nint dp[5000][5][5][5][5][5];\nclass Solution {\npublic:\n    int mod=1000000007;\n    \n     bool ch
```\n//just do n*3 and generalise case for 1,2,3,4,5 copy \nint dp[5000][5][5][5][5][5];\nclass Solution {\npublic:\n    int mod=1000000007;\n    \n     bool check(int a, int b, int c,int d,int e, int na, int nb, int nc,int nd,int ne){\n        if(na!=a && nb!=b &nc!=c && nd!=d && ne!=e && na!=nb && nb!=nc && nc!=nd && nd!=ne)return true;\n        return false;\n    }\n    \n    \n    \n    int sol(int i, int n, int a, int b, int c,int d,int e){\n        if(i==n)return 1;\n        if(dp[i][a+1][b+1][c+1][d+1][e+1]!=-1)return dp[i][a+1][b+1][c+1][d+1][e+1];\n        int ans=0;\n        for(int na=0;na<3;na++){\n            for(int nb=0;nb<3;nb++){\n                for(int nc=0;nc<3;nc++){\n                    for(int nd=0;nd<3;nd++){\n                for(int ne=0;ne<3;ne++){\n                    if(!check(a,b,c,d,e,na,nb,nc,nd,ne))continue;\n                    ans=(ans+sol(i+1,n,na,nb,nc,nd,ne))%mod;\n                }\n            }\n        }\n        }\n        }\n        return dp[i][a+1][b+1][c+1][d+1][e+1]=ans;\n    }\n    \n    \n    \n    bool check(int a, int b, int c,int d, int na, int nb, int nc,int nd){\n        if(na!=a && nb!=b &nc!=c && nd!=d && na!=nb && nb!=nc && nc!=nd )return true;\n        return false;\n    }\n    \n   \n    \n    int sol(int i, int n, int a, int b, int c,int d){\n        if(i==n)return 1;\n        if(dp[i][a+1][b+1][c+1][d+1][0]!=-1)return dp[i][a+1][b+1][c+1][d+1][0];\n        int ans=0;\n        for(int na=0;na<3;na++){\n            for(int nb=0;nb<3;nb++){\n                for(int nc=0;nc<3;nc++){\n                    for(int nd=0;nd<3;nd++){\n                {\n                    if(!check(a,b,c,d,na,nb,nc,nd))continue;\n                    ans=(ans+sol(i+1,n,na,nb,nc,nd))%mod;\n                }\n            }\n        }\n        }\n        }\n        return dp[i][a+1][b+1][c+1][d+1][0]=ans;\n    }\n     bool check(int a, int b, int c, int na, int nb, int nc){\n        if(na!=a && nb!=b &nc!=c && na!=nb & nb!=nc)return true;\n        return false;\n    }\n    //int dp[5000][4][4][4]; // it should be [3][3][3] nut since we have given in sol fuction so for the +1 thing we are taking one more\n    int sol(int i, int n, int a, int b, int c){\n        if(i==n)return 1;\n        if(dp[i][a+1][b+1][c+1][0][0]!=-1)return dp[i][a+1][b+1][c+1][0][0];\n        int ans=0;\n        for(int na=0;na<3;na++){\n            for(int nb=0;nb<3;nb++){\n                for(int nc=0;nc<3;nc++){\n                    if(!check(a,b,c,na,nb,nc))continue;\n                    ans=(ans+sol(i+1,n,na,nb,nc))%mod;\n                }\n            }\n        }\n        return dp[i][a+1][b+1][c+1][0][0]=ans;\n    }\n    \n     bool check(int a, int b, int na, int nb){\n        if(na!=a && nb!=b && na!=nb )return true;\n        return false;\n    }\n    //int dp[5000][4][4][4]; // it should be [3][3][3] nut since we have given in sol fuction so for the +1 thing we are taking one more\n    int sol(int i, int n, int a, int b){\n        if(i==n)return 1;\n        if(dp[i][a+1][b+1][0][0][0]!=-1)return dp[i][a+1][b+1][0][0][0];\n        int ans=0;\n        for(int na=0;na<3;na++){\n            for(int nb=0;nb<3;nb++){\n                {\n                    if(!check(a,b,na,nb))continue;\n                    ans=(ans+sol(i+1,n,na,nb))%mod;\n                }\n            }\n        }\n        return dp[i][a+1][b+1][0][0][0]=ans;\n    }\n    \n     bool check(int a, int na){\n        if(na!=a)return true;\n        return false;\n    }\n    //int dp[5000][4][4][4]; // it should be [3][3][3] nut since we have given in sol fuction so for the +1 thing we are taking one more\n    int sol(int i, int n, int a){\n        if(i==n)return 1;\n        if(dp[i][a+1][0][0][0][0]!=-1)return dp[i][a+1][0][0][0][0];\n        int ans=0;\n        for(int na=0;na<3;na++){\n            \n                {\n                    if(!check(a,na))continue;\n                    ans=(ans+sol(i+1,n,na))%mod;\n                }\n        }\n        return dp[i][a+1][0][0][0][0]=ans;\n    }\n    \n    int colorTheGrid(int n, int m) {\n        memset(dp,-1,sizeof (dp));\n        if (n==5)\n            return sol(0,m,-1,-1,-1,-1,-1);\n        if (n==4)\n            return sol(0,m,-1,-1,-1,-1);\n        if (n==3)\n            return sol(0,m,-1,-1,-1);\n        if (n==2)\n            return sol(0,m,-1,-1);\n        if (n==1)\n            return sol(0,m,-1);\n        return 0;\n    }   \n};
['C++']