#Program to compute the first n values of recurrence (42)  for Theta=1 in
#Clote, Kranakis, Krizanc:
#Asymptotics of Canonical and Saturatd RNA Secondary Structures

# D. Krizanc

def q(n):

    l = [0.,0.,0.,1.,1.]+[0.]*(n-4)

    for i in range(5,n+1):
        s=0.
        for k in range(1,i-1):
            s = s+l[k] + l[i-k-2]
        l[i] = 1. + s/(i-2)

    return l[n]/n
            
            
            
n=100000
print n, q(n)