#!/usr/bin/env python

import sys

def fib_rec(n):
    assert n >= 0
    if n < 2: return n
    return fib_rec(n - 2) + fib_rec(n - 1)

if __name__ == "__main__":
    print fib_rec(int(sys.argv[1]))

#!/usr/bin/env python

import sys

def bits(n):
    bits = []
    while n > 0:
            n, bit = divmod(n, 2)
            bits.append(bit)
    bits.reverse()
    return bits

def fib_mat(n):
    assert n >= 0
    a, b, c = 1, 0, 1
    for bit in bits(n):
        a, b, c = a*a + b*b, a*b + b*c, b*b + c*c
        if bit: a, b, c = b, c, b+c
    return b

if __name__ == "__main__":
    print fib_mat(int(sys.argv[1]))