Python 3 || Linear Transformations  || T/S: 99% / 97%
\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int, mod = 1_000_000_007) -> int:\n\n        if m == 1:\n            return 3*pow(2, n-1, mod) %mod\n
\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int, mod = 1_000_000_007) -> int:\n\n        if m == 1:\n            return 3*pow(2, n-1, mod) %mod\n\n        if m == 2:\n            return 2*pow(3, n, mod) %mod\n\n        if m == 3:\n            x0, x1 = 0, 3\n\n            for _ in range(n):\n                x0, x1 = ((3*x0 + 2*x1) %mod, \n                          (2*x0 + 2*x1) %mod)\n\n            return (x0+x1) %mod   \n\n        if m == 4:\n            x0, x1, x2 = 0, 2, 2\n\n            for _ in range(n):\n                x0, x1, x2 = ((3*x0 + 2*x1 +   x2) %mod,\n                              (4*x0 + 4*x1 + 2*x2) %mod,\n                              (  x0 +   x1 + 2*x2) %mod)\n\n            return (x0+ x1 + x2) %mod\n\n        if m == 5:\n            (x0, x1, x2, x3, x4, x5, x6, x7) = (0, 0, 0, 0, 3, 0, 3, 0)\n\n            for _ in range(n):\n\n                (x0, x1, x2, x3, x4, x5, x6, x7) = (\n\n                    (3*x0 + 2*x1 + 2*x2 +   x3 +          x5 + 2*x6 + 2*x7) %mod,\n                    (2*x0 + 2*x1 + 2*x2 +   x3 +   x4 +   x5 +   x6 +   x7) %mod,\n                    (2*x0 + 2*x1 + 2*x2 +   x3 +          x5 + 2*x6 + 2*x7) %mod,\n                    (1*x0 + 1*x1 + 1*x2 + 2*x3 +   x4 +   x5 +   x6 +   x7) %mod,\n                    (     + 1*x1 +      +   x3 + 2*x4 +   x5 +          x7) %mod,\n                    (1*x0 + 1*x1 + 1*x2 +   x3 +   x4 + 2*x5 +   x6 +   x7) %mod,\n                    (2*x0 + 1*x1 + 2*x2 +   x3 +          x5 + 2*x6 +   x7) %mod,\n                    (2*x0 + 1*x1 + 2*x2 +   x3 +   x4 +   x5 +   x6 + 2*x7) %mod )\n\n            return (x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7) %mod\n```\nhttps://leetcode.com/problems/painting-a-grid-with-three-different-colors/submissions/1357342872/\n\nI could be wrong, but I think that time complexity is *O*(*N*) and space complexity is *O*(1), in which *N* ~ `n`.\n\n\n\n
['Python3']