from fractions import Fraction as F

class Qsqrt5:
    def __repr__(self):
        return self.__str__()

    def __str__(self):
        if self.b == 0:
            return str(self.a)
        if self.a == 0:
            return "{0} sqrt(5)".format(str(self.b))
        return "{0} + {1} sqrt(5)".format(str(self.a), str(self.b))

    def __init__(self, a, b=0):
        self.a = F(a)
        self.b = F(b)

    ## Define arithmetic on Q[sqrt(5)], analogous to defining
    ## arithmetic on the complex numbers
    def __add__(self, other):
        return Qsqrt5(self.a + other.a, self.b + other.b)

    def __sub__(self, other):
        return Qsqrt5(self.a - other.a, self.b - other.b)

    def __mul__(self, other):
        return Qsqrt5(self.a*other.a + 5*self.b*other.b,
                      self.a*other.b + self.b*other.a)

    def inverse(self):
        denom = self.a**2 - 5*self.b**2
        return Qsqrt5(self.a/denom, -self.b/denom)

    def __div__(self, other):
        return self*other.inverse()

    def __pow__(self, n):
        if n == 0:
            return Qsqrt5(1)

        ## Do binary squaring
        halfpower = self**(n//2)
        return halfpower*halfpower*(self if n%2 == 1 else Qsqrt5(1))


phi1 = Qsqrt5(F(1,2), F(1,2))
phi2 = Qsqrt5(F(1,2), -F(1,2))

def fib(n):
    #Binet's formula
    return (phi1**n - phi2**n)/(phi1 - phi2)

print fib(1)
print fib(2)
print fib(3)
print fib(80)