import time


def mul(m1, m2):
    (a1, b1),\
    (c1, d1) = m1

    (a2, b2),\
    (c2, d2) = m2

    return [[a1 * a2 + b1 * c2, a1 * b2 + b1 * d2],
            [c1 * a2 + d1 * c2, c1 * b2 + d1 * d2]]


def mod(m, n):
    (a, b),\
    (c, d) = m

    return [[a % n, b % n],
            [c % n, d % n]]


fib_generator = [[1, 1],
                 [1, 0]]


one = [[1, 0],
       [0, 1]]


def modpow_log(m, p, n):
    binary_power = list("{0:b}".format(p))
    res = one
    mm = m
    for b in reversed(binary_power):
        if b == '1':
            res = mod(mul(res, mm), n)

        mm = mod(mul(mm, mm), n)

    return res


def fib_linear(x):
    if x < 2:
        return 1

    a = 1
    b = 1
    for i in xrange(x - 2):
        c = a + b
        a = b
        b = c

    return b


def modfib_mat_log(x, n):
    return modpow_log(fib_generator, x - 1, n)[0][0]

N = 123456
M = 12345

print "Linear algo, N =", N, "M =", M
start = time.clock()
print fib_linear(N) % M
end = time.clock()
print "time:", end - start

print "Log algo, N =", N, "M =", M
start = time.clock()
print modfib_mat_log(N, M)
end = time.clock()
print "time:", end - start

N = 123456789012345678
print "Log algo, N =", N, "M =", M
start = time.clock()
print modfib_mat_log(N, M)
end = time.clock()
print "time:", end - start