fibmod(n,m)[0] returns n-th nfibonacci number "mod m" -- in linear time [in O(log(n))] for constant m

fibmod.py

from sys import argv
#
def calc(t, m, odd):
    return ((t[1]**2 +     t[0]**2   ) % m, (t[1]**2 + 2*t[0]*t[1]) % m) if odd\
      else ((t[1]**2 - (t[1]-t[0])**2) % m, (t[1]**2 +   t[0]**2  ) % m)
#
def fibmod(n, m):
    if n==0:
        return (0, 1)
    elif n==1:
        return (1, 1)
    else:
        return calc(fibmod(n//2, m), m, n%2 == 1)
#    
print( fibmod(int(argv[1]), int(argv[2])) [0] )
#

Analysis and details:
https://pbs.twimg.com/media/E0-R4imXsAAoM0x?format=png&name=large