Background

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

Problem Description

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

Input Format

Input a positive integer $n$.

Output Format

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

5

5=5

6

8=2*2*2

Hint

$n \le 48$.

Translated by ChatGPT 5