A concise solution with matrix ops only (beat 100% java submissions)
java\nclass Solution {\n    public int colorTheGrid(int m, int n) {\n        long mod = 1_000_000_007;\n        long[][][] matrixs = {\n                { { 2 } 
```java\nclass Solution {\n    public int colorTheGrid(int m, int n) {\n        long mod = 1_000_000_007;\n        long[][][] matrixs = {\n                { { 2 } },\n                { { 3 } },\n                { { 3, 2 }, { 2, 2 } },\n                {\n                        { 3, 2, 1, 2 },\n                        { 2, 2, 1, 2 },\n                        { 1, 1, 2, 1 },\n                        { 2, 2, 1, 2 },\n                },\n                {\n                        { 3, 2, 2, 1, 0, 1, 2, 2 },\n                        { 2, 2, 2, 1, 1, 1, 1, 1 },\n                        { 2, 2, 2, 1, 0, 1, 2, 2 },\n                        { 1, 1, 1, 2, 1, 1, 1, 1 },\n                        { 0, 1, 0, 1, 2, 1, 0, 1 },\n                        { 1, 1, 1, 1, 1, 2, 1, 1 },\n                        { 2, 1, 2, 1, 0, 1, 2, 1 },\n                        { 2, 1, 2, 1, 1, 1, 1, 2 },\n                },\n        };\n        int len = m == 1 ? 1 : (int) (Math.pow(2, m - 2));\n        long[][] dp = new long[len][1];\n        for (long[] row : dp) {\n            row[0] = m == 1 ? 3 : 6;\n        }\n        long[][] matrix = matrixs[m - 1];\n        dp = multiply(matrixPower(matrix, n - 1, mod), dp, mod);\n        Long acc = 0l;\n        for (long[] row : dp) {\n            acc = (acc + row[0]) % mod;\n        }\n        return acc.intValue();\n    }\n\n    // matrix multiplication function\n    private long[][] multiply(long[][] a, long[][] b, long mod) {\n        int m = a.length, n = b[0].length, p = b.length;\n        long[][] c = new long[m][n];\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                for (int k = 0; k < p; k++) {\n                    c[i][j] += a[i][k] * b[k][j] % mod;\n                    c[i][j] %= mod;\n                }\n            }\n        }\n        return c;\n    }\n\n    // matrix fast power function\n    private long[][] matrixPower(long[][] matrix, long p, long mod) {\n        long[][] res = new long[matrix.length][matrix.length];\n        // initialized with the identity matrix\n        for (int i = 0; i < matrix.length; i++) {\n            res[i][i] = 1;\n        }\n        long[][] tmp = matrix;\n        // power decomposition\n        while (p != 0) {\n            if ((p & 1) != 0) {\n                res = multiply(res, tmp, mod);\n            }\n            tmp = multiply(tmp, tmp, mod);\n            p >>= 1;\n        }\n        return res;\n    }\n\n}\n```
['Dynamic Programming', 'Java']