from time import clock
import sys

def multiply( fibMatrix ):

    multiplicationMatrix = [ [1 , 1 ] , [ 1 , 0 ] ]
    global multicount
    global memory
    #i,j,k=0,0,0
	
    tempArr=[[0,0],[0,0]]

    for i in range(0, 2 ):
	
     for j in range(0 ,2):
		
        tempArr[i][j] = 0

        for k in range( 0, 2 ):
                    
            tempArr[i][j] = tempArr[i][j] + ( fibMatrix[i][k] * multiplicationMatrix[k][j] )
            multicount+=1
    memory+=sys.getsizeof(str(multiplicationMatrix))+sys.getsizeof(tempArr)+sys.getsizeof(i)+sys.getsizeof(j)+sys.getsizeof(k)
	# coping the values back from tempArray to fibMatrix

    for i in range(0 , 2 ):

        for j in range(0 ,2):

            fibMatrix[i][j] = tempArr[i][j]
		

def fibonacci(n):
    global memory
    if 1 == n :
        return 0
	
    if 2 == n :
        return 1
	
    fibMatrix = [ [ 1 , 1 ] , [ 1 , 0 ]]
    for i in range(1, n ):

        multiply( fibMatrix )
    memory+=sys.getsizeof(fibMatrix)

    return fibMatrix


start=clock()

multicount=0



infile=open('in2_4.txt','r')
n=int(infile.readline())
outfile=open('out_14_sec2_4.txt','w')
memory=0

f=fibonacci(n)

memory+=sys.getsizeof(start)+sys.getsizeof(multicount)+sys.getsizeof(infile)+sys.getsizeof(outfile)+sys.getsizeof(f)+sys.getsizeof(n)

outfile.write(str(n)+"="+str(f[1][0]))
outfile.write("\nno of multiplications "+str(multicount))
outfile.write("\nexecution time "+str(clock()-start))
outfile.write("\nmemory used "+str(memory)+" bytes")

print "output file generated"
infile.close()
outfile.close()