1. import sys
  2.  
  3. s = sys.stdin.readline().split(" ")
  4. n = int(s[0])
  5. m = int(s[1])
  6.  
  7. a = 0
  8. b = 1
  9. f = 1
  10. mem = [a, b]
  11.  
  12. for c in range(2, n+1):
  13.   f = (a + b) % m
  14.   a = b
  15.   b = f
  16.   if a == 0 and f == 1:
  17.      mem.pop()
  18.      break
  19.   else:
  20.      mem.append(f)
  21.  
  22. pos = n % len(mem)
  23. print(mem[pos])


Online example here: ideone.com/6pl4AR