P2626 Fibonacci Sequence (Upgraded Version)

Everyone knows that the Fibonacci sequence satisfies the following properties: - $f(1) = 1$. - $f(2) = 1$. - $f(n) = f(n-1) + f(n-2)$ (where $n > 2$ and $n$ is an integer).

Please compute the $n$-th Fibonacci number, take it $\bmod\,2^{31}$, and factor the result into prime factors.

Input a positive integer $n$.

Output the prime factorization of the $n$-th Fibonacci number after applying $\bmod\,2^{31}$.

$n \le 48$. Translated by ChatGPT 5