from functools import cache


@cache
def number_of_binary_trees(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        N = 0
        for i in range(0, n):
            N += number_of_binary_trees(i) * number_of_binary_trees(n-i-1)
        return N

@cache
def number_of_full_binary_trees(n):
    if n <= 1:
        return 1
    elif n%2 == 0:
        return 0
    else:
        N = 0
        # Only odd numbers possible.
        for nleft in range(1, n, 2):
            nright = n-1-nleft
            N += number_of_full_binary_trees(nleft) * number_of_full_binary_trees(nright)
        return N

@cache
def circle_chords(n):
    if n <= 1:
        return 0
    elif n == 2:
        return 1
    else:
        N = 0
        for i in range(0, n):
            for j in range(i+1, n):
                left = j - i - 1
                right = n - 2 - left
                N += 1 + circle_chords(left) * circle_chords(right)
        return N