1
class Solution:
2
    def colorTheGrid(self, m: int, n: int) -> int:
3
        from functools import reduce
4

5
        MOD = 10**9 + 7
6
        sum_mod = lambda x, y: (x + y) % MOD
7

8
        def normalize(pat_var):
9
            mapping = {e: i + 1 for i, e in enumerate(pat_var[0:2])}
10
            mapping[list({1, 2, 3}.difference(mapping.keys()))[0]] = 3
11
            return tuple([mapping[e] for e in pat_var])
12

13
        def get_pats(m, i, pat, pats):
14
            if i == m - 1:
15
                pats.append(tuple(pat))
16
                return
17
            i_nx = i + 1
18
            for p_it_nx in (1, 2, 3):
19
                if (i_nx <= 1 and p_it_nx == i_nx + 1) or (
20
                    i_nx >= 2 and p_it_nx != pat[-1]
21
                ):
22
                    pat.append(p_it_nx)
23
                    get_pats(m, i_nx, pat, pats)
24
                    pat.pop()
25
            return pats
26

27
        def get_trans(pat, i, pat_pre, trans):
28
            if i == len(pat) - 1:
29
                pat_nl = normalize(pat_pre)
30
                trans[pat_nl] = trans.get(pat_nl, 0) + 1
31
                return
32
            for p_it_pre in (1, 2, 3):
33
                i_nx = i + 1
34
                if p_it_pre != pat[i_nx] and (not pat_pre or p_it_pre != pat_pre[-1]):
35
                    pat_pre.append(p_it_pre)
36
                    get_trans(pat, i_nx, pat_pre, trans)
37
                    pat_pre.pop()
38
            return trans
39

40
        pats = get_pats(m, -1, [], [])
41
        # {pattern_i: {pattern_pre:count}}
42
        pat_trans = {pat: get_trans(pat, -1, [], {}) for pat in pats}
43

44
        p_counts = {pat: 1 for pat in pat_trans.keys()}
45
        for i in range(n - 1):
46
            p_counts_new = {}
47
            for pat, trans in pat_trans.items():
48
                p_counts_new[pat] = reduce(
49
                    sum_mod, (p_counts[pat_pre] * cnt for pat_pre, cnt in trans.items())
50
                )
51
            p_counts = p_counts_new
52

53
        res = reduce(sum_mod, (cnt for cnt in p_counts.values()))
54
        perms = reduce(lambda x, y: x * y, (3 - i for i in range(min(3, m))))
55
        return (res * perms) % MOD