1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

from __future__ import division

def matrix_mult(A, B):
    C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 10**8
    return C

def fast_exponentiation(A, n):
    if n == 1:
        return A
    else:
        if n % 2 == 0:
            A1 = fast_exponentiation(A, n // 2)
            return matrix_mult(A1, A1)
        else:
            return matrix_mult(A, fast_exponentiation(A, n - 1))

def solve(n):
    A = [[0,0,-2],[1,0,0],[0,1,4]]
    A_n = fast_exponentiation(A, n) #(A, n-3)
    print (A_n)

if __name__ == "__main__":
    solve(987654321)