fibo.py

import numpy as np

def fibonacci(n):
    def fast_mod(base, exp, mod):
        base = base % mod
        res = 1
        while exp > 0:
            if exp & 1:
                res = (res * base) % mod
            base = base * base % mod
            exp >>= 1
        return res

    base = np.matrix([[0, 1], [1, 1]])
    return (fast_mod(base ,n, 1000000) * np.matrix([[1, 0], [0, 1]]))[0, 1]


for i in xrange(10):
    print fibonacci(i+1)