# xs = list(divmod(i, 4) for i in range(16))
# dct = dict(zip("ABCDEFGIJLMNOP", xs))
# from collections import defaultdict
# # print(dct)

# def are_aligned(p1, p2, p3):
#     det = (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])
#     k = (p2[0] - p1[0]) / (p3[0] - p1[0]) if p3[0] != p1[0] else (p2[1] - p1[1]) / (p3[1] - p1[1])
#     same = 0 < k < 1
#     return det == 0 and same

# unsafe = defaultdict(set)
# from itertools import combinations
# for p1, p2, p3 in combinations(xs, r=3):
#     if are_aligned(p1, p2, p3):
#         unsafe[(p1, p3)].add(p2)
#         unsafe[(p3, p1)].add(p2)
# # print(unsafe)
                
# def cnt(c):
#     d = {i: 0 for i in range(16)}
#     q = [[dct[c]]]
#     visited = set()
#     c = 0
#     while c < 20:
#         path = q.pop()
#         print(path)
#         x, y = path[-1]
#         d[len(path) - 1] += 1
#         for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1)):
#             u, v = x + dx, y + dy
#             p = set(path)
#             if 0 <= u < 4 and 0 <= v < 4 and not (u, v) in p:
#                 e = path[-1]
#                 unvisited = unsafe[(e, (u, v))] - p
                
#                 if len(unvisited) == 0:
#                     print((x, y), "=>", (u, v))
#                     q.append(path + [(u, v)])
#         c += 1
#     return d
from functools import cache
G = {
    'a': set('bed'),
    'b': set('cfeda'),
    'c': set('feb'),
    'd': set('abehg'),
    'e': set('bcfihgda'),
    'f': set('ciheb'),
    'g': set('deh'),
    'h': set('efigd'),
    'i': set('fhe')
}
visited = {c: False for c in "abcdefghijklmnop"}
result = 0
@cache
def count_patterns(node, length):
    if length == 1:
        return len(G[node])
    global result
    for neighbor in G[node]:
        if not visited[neighbor]:
             visited[neighbor] = True
             result += count_patterns(neighbor, length - 1)
             visited[neighbor] = False
    return result
r = count_patterns('a', 2)    
print(r)