def course(f,N,a):
    seq = [a]
    i = 1
    while i<N:
      a = f(a)
      seq.append(a)
      i = i + 1
    return seq

def iterate(f,n,a):
    i = 0
    while i!=n:
        a = f(a)
        i = i + 1
    return a

def repcourse(f,a):
    pper = []
    while a not in pper:
        pper.append(a)
        a = f(a)
    i = pper.index(a)
    return [pper[:i],pper[i:]]

def factorial(n):
    i, fact = 0, 1
    while i<n:
        i, fact = i + 1, fact * (n - i)
    return fact

def comb(n,k):
    list0 = (n - k + 1) * [1]
    i = j = 0
    while i<k:
        list1 = [1]
        while j<n-k:
            j = j + 1
            list1.append(list1[-1] + list0[j])
        list0 = list1
        i, j = i + 1, 0
    return list0[-1]

def combrow(n):
    m=0
    row=[1]
    while m<n:
        row = [0] + row + [0]
        row = [row[i] + row[i + 1] for i in range(m + 2)]
        m=m+1
    return row

def bernoulli(n):
    if n==0: return [(1,1)]
    if n==1: return [(1,1),(-1,2)]
    else:
        m = 1
        row = [1, 2, 1]
        bernoul = [(1, 1), (-1, 2)]
        while m<n:
            m = m + 1
            row = [0] + row + [0]
            row = [row[i] + row[i + 1] for i in range(m + 2)]
            bernnew = [mul((row[i],1), bernoul[i]) for i in range(m)]
            bernoul.append(mul(reduce(add,bernnew),(-1,m + 1)))
        return bernoul

def stirling2(n,k):
    list0 = [1] + (n - k) * [0]
    i = j = 0
    while i<k:
        list1 = [1]
        i = i + 1
        while j<n-k:
            j = j + 1
            list1.append(i * list1[-1] + list0[j])
        list0 = list1
        j = 0
    return list0[-1]

def stirling1(n,k):
    list0 = [1] + (n - k) * [0]
    i = j = 0
    while i<k:
        list1 = [1]
        i = i + 1
        while j<n-k:
            j = j + 1
            list1.append((i + j - 1) * list1[-1] + list0[j])
        list0=list1
        j = 0
    return list0[-1]

def transpositions(perm):
    trans = []
    newperm = perm[:]
    identity = range(1, len(perm) + 1)
    while newperm!=identity:
        j = [i+1==newperm[i] for i in
        range(len(newperm))].index(0)
        trans.append((j + 1, newperm[j]))
        newperm[newperm.index(j+1)]=newperm[j]
        newperm[j] = j + 1
    return trans

def cycledecomposition(perm):
    sublist = perm[:]
    cycles = []
    while sublist!=[]:
        i = sublist[0]
        cycle=(i,)
        j = perm[i-1]
        del sublist[0]
        while j!=i:
            cycle = cycle + (j,)
            sublist.remove(j)
            j = perm[j-1]
        cycles.append(cycle)
    return cycles

def sign(perm):
    return (-1)**(len(perm) - len(cycledecomposition(perm)))

def permutation1(cycle,n):
    i = 0
    perm = []
    cyclelist = list(cycle)
    while i<n:
        i = i + 1
        if i in cycle and i!=cycle[-1]:
            perm.append(cycle[cyclelist.index(i) + 1])
        elif i==cycle[-1]:
            perm.append(cycle[0])
        else:
            perm.append(i)
    return perm

def composition(perm1,perm2):
    return [perm1[perm2[i] - 1] for i in range(len(perm2))]

def permutation(cycles,n):
    return reduce(composition,[permutation1(cycle,n) for 
    cycle in cycles])