# -*- coding: utf-8 -*-
def fib1(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    a=0
    b=1
    for i in range(1, n):
        a, b = b, b + a
    return b

def fib2(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib2(n - 1) + fib2(n - 2)

def fib3(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n % 2 == 0:
        a = fib3(n // 2)
        b = fib3(n // 2 - 1)
        return (2 * b + a) * a
    else:
        a = fib3((n + 1) // 2)
        b = fib3((n + 1) // 2 - 1)
        return a ** 2 + b ** 2

def fib4(n, d):
    if n in d:
        return d[n]
    if n <= 1:
        d[n] = n
        return n
    if n % 2 == 0:
        a = fib4(n // 2, d)
        b = fib4(n // 2 - 1, d)
        r = (2 * b + a) * a
        d[n] = r
        return r
    a = fib4((n + 1) // 2, d)
    b = fib4((n + 1) // 2 - 1, d)
    r = a ** 2 + b ** 2
    d[n] = r
    return r

for i in range(20):
    assert(fib1(i) == fib2(i))
    assert(fib1(i) == fib3(i))
    assert(fib1(i) == fib4(i, {}))