def matrix_multiply(A,B,m):
    return [ [ ( A[r][0]*B[0][c] + A[r][1]*B[1][c] ) % m for c in range(2) ] for r in range(2) ]
 
def matrix_power(A,n,m):
    if n==0: return [ [1%m,0], [0,1%m] ] # identity modulo m
    B = matrix_power(A,n//2,m)
    C = matrix_multiply(B,B,m)
    if n%2==1: C = matrix_multiply(C,A,m)
    return C
 
def modular_fibonacci(n,m):
    A = matrix_power( [ [0,1], [1,1] ], n, m )
    return A[1][0]
 
for n in range(10): print( modular_fibonacci( n, 10**9 ) )
print( modular_fibonacci( 10**100, 10**9 ) )

ZGVmIG1hdHJpeF9tdWx0aXBseShBLEIsbSk6CiAgICByZXR1cm4gWyBbICggQVtyXVswXSpCWzBdW2NdICsgQVtyXVsxXSpCWzFdW2NdICkgJSBtIGZvciBjIGluIHJhbmdlKDIpIF0gZm9yIHIgaW4gcmFuZ2UoMikgXQoKZGVmIG1hdHJpeF9wb3dlcihBLG4sbSk6CiAgICBpZiBuPT0wOiByZXR1cm4gWyBbMSVtLDBdLCBbMCwxJW1dIF0gIyBpZGVudGl0eSBtb2R1bG8gbQogICAgQiA9IG1hdHJpeF9wb3dlcihBLG4vLzIsbSkKICAgIEMgPSBtYXRyaXhfbXVsdGlwbHkoQixCLG0pCiAgICBpZiBuJTI9PTE6IEMgPSBtYXRyaXhfbXVsdGlwbHkoQyxBLG0pCiAgICByZXR1cm4gQwoKZGVmIG1vZHVsYXJfZmlib25hY2NpKG4sbSk6CiAgICBBID0gbWF0cml4X3Bvd2VyKCBbIFswLDFdLCBbMSwxXSBdLCBuLCBtICkKICAgIHJldHVybiBBWzFdWzBdCgpmb3IgbiBpbiByYW5nZSgxMCk6IHByaW50KCBtb2R1bGFyX2ZpYm9uYWNjaSggbiwgMTAqKjkgKSApCnByaW50KCBtb2R1bGFyX2ZpYm9uYWNjaSggMTAqKjEwMCwgMTAqKjkgKSAp