class Solution(object):
def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""
def count(i, X, cache={}):
if i < 2: return 1
if X not in cache: # X: set of still avaliable numbers
cache[X] = sum(count(i-1, X-{x}) for x in X
if x%i == 0 or i % x == 0)
return cache[X]
return count(N, frozenset(range(1, N + 1))) # use frozenset to ensure the fixed order