import random, math,itertools

def perm_cal(j,positions):
    boson_a = j
    perm_cycle = []
    while True:
        perm_cycle.append(boson_a)
        boson_b = positions.pop(boson_a)
        if boson_b == perm_cycle[0]:
            break
        else:
            boson_a = boson_b
    k = len(perm_cycle)
    return perm_cycle, k

        

N = 100
nsteps = 10000
positions = {}
acc=0
for i in range(N):
    positions[i]=i
for i in range(nsteps):
    for j in range(N):
        cycle, k= perm_cal(j, positions)
        positions[cycle[-1]] = cycle[0]
        for l in range(len(cycle) - 1):
            positions[cycle[l]] = cycle[l + 1]
        if k > N/2:
            break
    if j ==N-1:
        acc+=1
    a=random.choice(positions.keys())
    a_1=positions[a]
    b=random.choice(positions.keys())
    b_1=positions[b]
    positions[a]=b_1
    positions[b]=a_1
print acc/float(nsteps)