"""
012
345
678
"""

def adj(path,to):
    fr = path[-1] # from; i.e. last node in path
    if to in path:
        return False
    # to is not visited yet
    elif fr==4:
        return True
    elif fr in [1,3,5,7]:
        return fr+to!=8 or 4 in path
    # from in [0,2,6,8]
    elif to in [0,2,6,8]:
        return (fr+to)/2 in path
    # to in [1,3,4,5,6,7]
    return True

nodes = range(9)

counter = 0

def traversal(path = []):
    global counter
    counter += 1
    for x in nodes:
        if adj(path,x):
            traversal(path + [x])

for x in nodes:
    traversal([x])
print counter

#The result is 389497