Calcula el término n-ésimo de Fibonacci módulo m
La secuencia de Fibonacci se define al obtener cada nuevo término sumando los dos anteriores, mientras que los dos primeros elementos son 0 y 1:
Dado el número n, se te pide calcular el n-ésimo número de Fibonacci módulo m.
Como únicamente nos interesa el resultado módulo m, el valor de n puede ser muy grande.
Entrada
La única línea de la entrada contiene dos enteros n (0 ≤ n ≤ ) y m (1 ≤ m ≤ 50).
Salida
El programa debe imprimir el resultado de .
Ejemplos
Entrada | Salida |
|---|---|
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Explicación
fib(0) = 0 ⇒ 0 mod 5 = 0
fib(1) = 1 ⇒ 1 mod 5 = 1
fib(6) = 8 ⇒ 8 mod 5 = 3
Pista 1
Como estamos calculando los números de Fibonacci módulo m, y cada nuevo número depende de los dos anteriores, en algún momento los valores empiezan a repetirse. Puedes intentar imprimir muchos valores módulo m para notar el patrón que se repite.
Pista 2
Dado que los valores se repiten en cierto punto, puedes calcular directamente el n-ésimo número de Fibonacci sin necesidad de recorrerlos todos.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB