Fastest O(n) Python Solution
The solution is completely similar to recurrent one of problem 1411. Memory complexity is O(1).\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -
The solution is completely similar to recurrent one of problem 1411. Memory complexity is O(1).\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n\n        if m == 1:\n            return 3 * 2**(n-1) % 1000000007\n\n        if m == 2:\n            return 6 * 3**(n-1) % 1000000007\n\n        if m == 3:\n            (a, b) = (6, 6)\n            for _ in range(n-1):\n                a = 2*(a + b)\n                b = a + b\n            return (a + b) % 1000000007\n\n        if m == 4:\n            (a, b, c) = (6, 12, 6)\n            for _ in range(n-1):\n                (a, b, c) = (2*a + b  + c, \n                             2*a + 4*(b + c),\n                             a + 2*b + 3*c)\n            return (a + b + c) % 1000000007\n\n        if m == 5:\n            (a, b, c, d, e, f) = (6, 12, 6, 12, 6, 6)\n            for _ in range(n-1):\n                (a, c, d, e) = (2*a + b + d, \n                                b + d + 2*(c + e + f),\n                                2*(a + b + c) + 3*d + 4*(e + f),\n                                b + 2*(c + d + e + f))\n                b += a + c\n                f += e\n            return (a + b + c + d + e + f) % 1000000007\n```
[]