def pisano(m):
	if m == 1:
		return 1
 
	"""
	toda sequência tem tamanho par, então posso começar de n = 2 e terminar quando
	obter:
 
	f_n_minus_1 == 0
	f_n == 1
	"""
 
	f_n_minus_1 = 1
	f_n = 1
	n = 2
 
	while not(f_n_minus_1 == 0 and f_n == 1):
		f_n_plus_1 = (f_n + f_n_minus_1) % m
		f_n_minus_1 = f_n
		f_n = f_n_plus_1
		n += 1
	return n - 1
 
def fib_mod(n, m):
  n = n % pisano(m)
  if n == 0:
    return 0
  f_x_minus_1 = 0
  f_x = 1
  x = 1
  while x < n:
    f_x_plus_1 = (f_x + f_x_minus_1) % m
    f_x_minus_1 = f_x
    f_x = f_x_plus_1
    x += 1
  return f_x
 
def fib_fib_mod(n, m):
  return fib_mod(fib_mod(n, pisano(m)), m)
 
 
for (n, m) in ((1,100),(2,100),(3,100),(4,100),(5,100),(5,2),(6,100), (10**9,10)):
  print("fib_fib_mod({}, {}) = {}".format(n, m, fib_fib_mod(n, m)))
 
 

ZGVmIHBpc2FubyhtKToKCWlmIG0gPT0gMToKCQlyZXR1cm4gMQoJCQoJIiIiCgl0b2RhIHNlcXXDqm5jaWEgdGVtIHRhbWFuaG8gcGFyLCBlbnTDo28gcG9zc28gY29tZcOnYXIgZGUgbiA9IDIgZSB0ZXJtaW5hciBxdWFuZG8KCW9idGVyOgoJCglmX25fbWludXNfMSA9PSAwCglmX24gPT0gMQoJIiIiCgkKCWZfbl9taW51c18xID0gMQoJZl9uID0gMQoJbiA9IDIKCQoJd2hpbGUgbm90KGZfbl9taW51c18xID09IDAgYW5kIGZfbiA9PSAxKToKCQlmX25fcGx1c18xID0gKGZfbiArIGZfbl9taW51c18xKSAlIG0KCQlmX25fbWludXNfMSA9IGZfbgoJCWZfbiA9IGZfbl9wbHVzXzEKCQluICs9IDEKCXJldHVybiBuIC0gMQoJCmRlZiBmaWJfbW9kKG4sIG0pOgogIG4gPSBuICUgcGlzYW5vKG0pCiAgaWYgbiA9PSAwOgogICAgcmV0dXJuIDAKICBmX3hfbWludXNfMSA9IDAKICBmX3ggPSAxCiAgeCA9IDEKICB3aGlsZSB4IDwgbjoKICAgIGZfeF9wbHVzXzEgPSAoZl94ICsgZl94X21pbnVzXzEpICUgbQogICAgZl94X21pbnVzXzEgPSBmX3gKICAgIGZfeCA9IGZfeF9wbHVzXzEKICAgIHggKz0gMQogIHJldHVybiBmX3gKCmRlZiBmaWJfZmliX21vZChuLCBtKToKICByZXR1cm4gZmliX21vZChmaWJfbW9kKG4sIHBpc2FubyhtKSksIG0pCiAgCiAgCmZvciAobiwgbSkgaW4gKCgxLDEwMCksKDIsMTAwKSwoMywxMDApLCg0LDEwMCksKDUsMTAwKSwoNSwyKSwoNiwxMDApLCAoMTAqKjksMTApKToKICBwcmludCgiZmliX2ZpYl9tb2Qoe30sIHt9KSA9IHt9Ii5mb3JtYXQobiwgbSwgZmliX2ZpYl9tb2QobiwgbSkpKQoK