def fibonacci1(n):
    phi = (1 + 5 ** 0.5) / 2
    phicap = (1 - 5 ** 0.5) / 2
    return round((1/5**0.5)*(pow(phi,n)-pow(phicap,n)))

def fibonacci2(n):
    if n in {1, 2}: # Base case
        return 1
    else: 	
    	return fibonacci2(n-1) + fibonacci2(n-2)

def fibonacci3(n):
    if n == 0: return 0
    if n <= 2: return 1

    # Initialize the array with zeros
    # We need n + 1 slots to include the n-th index
    Fib = [0] * (n + 1)
    # Base cases
    Fib[1] = 1
    Fib[2] = 1

    for i in range(3, n+1):
        # Calculate the next value by adding the last two values
        Fib[i] = Fib[i-1] + Fib[i-2]
    
    return Fib[n]


import time
if __name__ == '__main__':
    n = int(input("Enter n: "))

    print("Running fibonacci1...")
    start_time = time.time()
    res = fibonacci1(n)
    t = time.time() - start_time
    print("fibonacci1:", "F(", n, ")=", res, "time=", t, "sec.")

    print("Running fibonacci3...")
    start_time = time.time()
    res = fibonacci3(n)
    t = time.time() - start_time
    print("fibonacci3:", "F(", n, ")=", res, "time=", t, "sec.")

    print("Running fibonacci2...")
    start_time = time.time()
    res = fibonacci2(n)
    t = time.time() - start_time
    print("fibonacci2:", "F(", n, ")=", res, "time=", t, "sec.")