Easy Java, comments, 28ms, O(n*P*P) complexity, memory O(P), where P is column permutations count
\nclass Solution {\n    public int colorTheGrid(int m, int n) {\n        //each permutation will be encoded as Long where every color will be packed into 0xFF b
```\nclass Solution {\n    public int colorTheGrid(int m, int n) {\n        //each permutation will be encoded as Long where every color will be packed into 0xFF byte \n        //for example RGB combination will be represented as 0x010204\n        //while BGRGB combination will be 0x0402010204\n        final long R = 1;\n        final long G = 2;\n        final long B = 4;\n        final int MOD =1000000007;\n        \n        //compute overall number of possible permutations for a single column\n        int COUNT = 3;\n        for(int i=0;i<m-1;i++)\n            COUNT*=2;\n        \n        long[] perms = new long[COUNT];\n        Queue<Long> q = new LinkedList<>();\n                \n        q.add(R);\n        q.add(G);\n        q.add(B);\n        \n        //fill in all possible permuatations using Queue\n        int ind = COUNT;\n        while(!q.isEmpty()){\n            Long l  = q.poll();\n            if( l >=  1L << 8*(m-1) ) //m-length permutation\n                perms[--ind] = l;\n            else{\n                if( (l & R) != 0 ){\n                    q.add( (l<<8) + G);\n                    q.add( (l<<8) + B);\n                }else if( (l & B) != 0 ){\n                    q.add( (l<<8) + R);\n                    q.add( (l<<8) + G);\n                }else{\n                    q.add( (l<<8) + R);\n                    q.add( (l<<8) + B);\n                }\n            }\n        }\n        \n        \n        \n        int[] prev = new int[COUNT];\n        int[] curr = new int[COUNT];\n        Arrays.fill(prev, 1);\n        \n        //iterate by columns from left to right, \n        //memorizing score count for every permutation in previous column\n        for(int iter=0;iter<n-1;iter++){\n            for(int i=0;i<COUNT;i++){\n                for(int j=0;j<COUNT;j++){\n                    if((perms[i] & perms[j]) == 0) // both are OK to each other \n                        curr[j] = (curr[j]+prev[i])%MOD;\n\n                }\n            }\n            //swap buffers and erase\n            int[] t = prev;\n            prev = curr;\n            curr = t;\n            Arrays.fill(curr,0);\n        }\n        \n        //accumulate all scores for permuttions as per last collumn \n        int result = 0;\n        for(int i=0;i<COUNT;i++)\n            result = (result + prev[i])%MOD;\n        \n        return result;    \n    }\n}\n```
[]