Dos igualdades sorprendentes
Los matemáticos a lo largo de la historia han encontrado igualdades sorprendentes. La que seguramente sea la más famosa de todas ellas es la conocida como identidad de Euler que relaciona los dos números irracionales más conocidos, π y e con el número indispensable para construir números complejos, i, y los dos números básicos de la aritmética, el 0 y el 1:
\[e^{i\pi} + 1 = 0\]Según cuentan, Gauss dijo sobre ella que aquellos a los que no les pareciera una igualdad obvia nada más verla nunca llegarían a ser matemáticos de primer nivel.
Otra igualdad sorprendente pero al alcance de mentes menos privilegiadas es la que relaciona los números de Fibonacci con el cálculo de matrices. Recordemos que los números de Fibonacci son:
fib0 = 0, fib1 = 1, fibn = fibn-1 + fibn-2
Pues bien, si partimos de la matriz de 2×2 \(\left(\begin{matrix}0 & 1 \\ 1 & 1\end{matrix}\right)\) resulta que:
\[\left(\begin{matrix}0 & 1 \\ 1 & 1\end{matrix}\right)^n = \left(\begin{matrix}fib_{n-1} & fib_n \\ fib_n & fib_{n+1}\end{matrix}\right)~~~~\forall n \ge 1\]Eso significa que se puede utilizar cálculo matricial para obtener un número de Fibonacci dado.
Entrada
Cada caso de prueba consiste en una única línea con un número entero no negativo, n. Se garantiza que el número no será mayor que 231−1.
La entrada terminará cuando se lea un cero; ese caso no deberá generar salida.
Salida
Para cada caso de prueba se escribirá el número de Fibonacci correspondiente, fibn, módulo 46.337.
Entrada de ejemplo
1 2 4 22 23 24 0
Salida de ejemplo
1 1 3 17711 28657 31