from time import clock
import sys
mem = 0
mult = 0
t=0
infile = open('in2_4.txt','r')
c1=clock()
n = int(infile.read())
mem = 0
mult =0
# values stored in list instead of 2Darray
std=[1,1,0,1] # 00 01 11 10

def mat_mult(p,q):
    a = []
    a.insert( 0, ( p[0] * q[0] ) + ( p[1] * q[3] )  )
    a.insert( 1,( p[0] * q[1] ) + ( p[1] * q[2] )  )
    a.insert( 2,( p[3] * q[1] ) + ( p[2] * q[2] )  )
    a.insert( 3,( p[3] * q[0] ) + ( p[2] * q[3] )  )
    #a.insert( 0, p[0]  + p[1] )
    #a.insert( 1,p[0] )
    #a.insert( 2,p[3] )
    #a.insert( 3,p[3]+p[2])
    
    global mult
    mult = mult + 8
    global mem
    mem =  mem + sys.getsizeof(a)
    #print a
    return a #, mul , size
    

def mat_power(x,y):
    
    if y==1:
        return x 
    elif y==2:
        
        return mat_mult(x,x)
        
    else:
        if y%2 == 0:
            mat =   mat_power(x,y/2)
            return mat_power( mat,2)
        else:
            mat = mat_power(x,y/2)
            mat1 = mat_power(mat, 2)
            return mat_mult( mat1, x)


fib= mat_power(std,n)
mem = mem + sys.getsizeof(fib) + sys.getsizeof(t) + sys.getsizeof(c1) + sys.getsizeof(mult)
t = clock()-c1
string = str(n)+'='+ str(fib[1])
string = string +"\n"+"MULTIPLICATIONS="+ str(mult) #multiplications
string = string +','+"TIME="+(str(t)) #timetaken
string = string +','+"MEMORY="+(str(mem))#memory used
#print string
outfile = open('out_4_2_4.txt','w')
outfile.write(string)
outfile.close()