# by Tim Ratigan
# counts randomly sampled permutations and produces the ratio of permutations
# without 1- or 2-cycles

from random import shuffle

def contains12cycle ( perm ): # function to check if there is a 1- or 2-cycle
    N = len(perm)
    for x in range (N):
        if perm[perm[x]] == x:
            return True
    return False

N = 20 # size of permutations
tests = 1000000 # number of trials
total = 0.0 # count variable

# randomly generate permutations of length N, count the ones not containing
# a 1- or a 2- cycle
for x in range(tests):
    perm = range(N)
    shuffle(perm)
    if not contains12cycle( perm ):
        total += 1.0

print total/tests # print ratio