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)))