Java Solution with Fast matrix power
1. Group possible paintings of a row to their templates and find number of painting of each template.\n#2. Find for each template pair how many paintings of sec
#1. Group possible paintings of a row to their templates and find number of painting of each template.\n#2. Find for each template pair how many paintings of second template can be after each painting of first template.\n#3. create vector A with number of possible paintings of one row for each template (as said in #1).\n#4. create matrix B from number from #2\n#5. calculate A*B^(n-1)\n#6. Calculate sum of elements in #5\n\nCompelxity of multiplying:\nnumber of rows in matrix N= 2^(m-2)\none multiplication takes - O(N^3)\nnumber of multiplication - O(logN)\n\nTotal complexity - O(8^m * logN), or can be considered as O(logN) as m is very strictly limited and both A and B can be computed ahead-of-time.\n\n#Update\nNumber of painting for each template is 6, and solution can be simplified.\n\n```\n\nimport java.util.HashMap;\nimport java.util.Map;\n\npublic class Solution {\n    public static final int p = 1_000_000_007;\n\n    public int colorTheGrid(int m, int n) {\n        if (m == 1) return (int) (3L * powMod(2, n - 1) % p);\n        if (m == 2) return (int) (6L * powMod(3, n - 1) % p);\n        if (n == 1) return (int) (3L * powMod(2, m - 1) % p);\n        if (n == 2) return (int) (6L * powMod(3, m - 1) % p);\n\n        int totalTemplates = 1 << (m - 2);\n        int totalPaintings = binPow(3, m);\n\n        int[] paintingToTemplate = new int[totalPaintings];\n        long[] paintingCountForTemplate = new long[totalTemplates];\n        long[][] templateEdgeCount = new long[totalTemplates][totalTemplates];\n\n        Map<Integer, Integer> templateToIndex = new HashMap<>(1 << (m - 2));\n\n        int templateCounter = 0;\n        for (int i = 0; i < totalPaintings; i++) {\n            int type = getType(i, m);\n            if (type == -1) {\n                paintingToTemplate[i] = -1;\n                continue;\n            }\n            Integer templateIndex = templateToIndex.get(type);\n            if (templateIndex == null) {\n                templateToIndex.put(type, templateCounter);\n                templateIndex = templateCounter++;\n            }\n            paintingToTemplate[i] = templateIndex;\n            paintingCountForTemplate[templateIndex]++;\n        }\n        for (int i = 0; i < totalPaintings; i++) {\n            if (paintingToTemplate[i] == -1) continue;\n            for (int j = i + 1; j < totalPaintings; j++) {\n                if (paintingToTemplate[j] == -1) continue;\n                if (checkAllowance(i, j, m)) {\n                    templateEdgeCount[paintingToTemplate[i]][paintingToTemplate[j]]++;\n                    templateEdgeCount[paintingToTemplate[j]][paintingToTemplate[i]]++;\n                }\n            }\n        }\n        for (int i = 0; i < totalTemplates; i++) {\n            long c = paintingCountForTemplate[i];\n            for (int j = 0; j < totalTemplates; j++) {\n                templateEdgeCount[i][j] /= c;\n            }\n        }\n\n        long[][] matrixPower = matrixPower(templateEdgeCount, n - 1);\n        long ans = 0;\n        for (int i = 0; i < totalTemplates; i++) {\n            long s = 0;\n            long[] arr = matrixPower[i];\n            for (long a : arr) s += a;\n            ans += paintingCountForTemplate[i] * s;\n        }\n        return (int) (ans % p);\n    }\n\n    private static boolean checkAllowance(int a, int b, int m) {\n        for (int i = 0; i < m; i++) {\n            if (a % 3 == b % 3) return false;\n            a /= 3;\n            b /= 3;\n        }\n        return true;\n    }\n\n    private static int getType(int a, int m) {\n        int[] digits = new int[3];\n        int first = a % 3;\n        int second = a % 9 / 3;\n        if (first == second) return -1;\n        digits[second] = 1;\n        digits[3 - first - second] = 2;\n        int prev = second;\n        int type = 1;\n        m -= 2;\n        a /= 9;\n        while (m-- > 0) {\n            int curr = a % 3;\n            if (prev == curr) return -1;\n            type = type * 3 + digits[curr];\n            prev = curr;\n            a /= 3;\n        }\n        return type;\n    }\n\n    private static int powMod(int a, int b) {\n        long res = 1;\n        while (b != 0)\n            if ((b & 1) != 0) {\n                res = (res * a) % p;\n                --b;\n            } else {\n                a = (int) (((long) a * a) % p);\n                b >>= 1;\n            }\n        return (int) res;\n    }\n\n    private static int binPow(int a, int n) {\n        int res = 1;\n        int tmp = a;\n        while (n != 0) {\n            if ((n & 1) != 0)\n                res *= tmp;\n            tmp *= tmp;\n            n >>= 1;\n        }\n        return res;\n    }\n\n    private static long[][] matrixPower(long[][] base, long pow) {\n        int n = base.length;\n        long[][] res = new long[n][n];\n        for (int i = 0; i < n; i++) {\n            res[i][i] = 1;\n        }\n        while (pow != 0) {\n            if ((pow & 1) != 0) {\n                res = multiplyMatrix(res, base);\n                --pow;\n            } else {\n                base = multiplyMatrix(base, base);\n                pow >>= 1;\n            }\n        }\n        return res;\n    }\n\n    private static long[][] multiplyMatrix(long[][] a, long[][] b) {\n        int n = a.length;\n        long[][] ans = new long[n][n];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                for (int k = 0; k < n; k++) {\n                    ans[i][j] += a[i][k] * b[k][j];\n                }\n                ans[i][j] %= p;\n            }\n        }\n        return ans;\n    }\n}\n\n```
['Dynamic Programming', 'Java']