tree.py

MAXN = 1429

HtoN = [1,2]
while HtoN[-1] <= MAXN*20:
    HtoN.append(HtoN[-1] + HtoN[-2] + 1)

argvar = 0

NtoH = [-1]
curh = 0
for n in range(1,MAXN):
    if n > HtoN[curh]:
        curh += 1
    NtoH.append(curh)
    
NtoMinH = [-1,0,1]
Min = 4
log = 1
for n in range(3,MAXN):
    if Min & n:
        Min <<= 1
        log += 1
    NtoMinH.append(log)
    
'''
Everything above here is not strictly necessary to solve the problem, only to make it faster
'''
Treenums = [[0 for x in range(MAXN)] for h in range(25)]
Treenums[0][1] = 1
Treenums[1][2] = 2
Treenums[1][3] = 1
     
for n in range(4,MAXN-1):
    splitn = n-1
    for h in range(NtoMinH[n]-1,NtoH[n]):
        sum = 0
        minn = 0 if h == 0 else HtoN[h-1]
        lowl = Treenums[h-1]
        highl = Treenums[h]
        for x in range(minn,splitn+1-minn):
            y = splitn - x
            sum += highl[x] * highl[y]
            sum += lowl[x] * highl[y]
            sum += highl[x] * lowl[y]
            
        Treenums[h+1][n] += sum

import sys

for instr in sys.stdin.readlines():
    n = int(instr)
    
    num = 0
    for h in range(15):
        num += Treenums[h][n]
    
    s = ""
    for i in range(9):
        s += str(num%10)
        num //= 10
        
    print(s[::-1])#reverses string