Problem Background

As everyone knows, the Fibonacci sequence is a series that 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 value of the $n$-th number in the Fibonacci sequence modulo $2^{31}$, and then decompose it into its prime factors.

Input Format

Input a positive integer $n$.

Output Format

Decompose the $n$-th number in the Fibonacci sequence into its prime factors.

Sample Input and Output

Sample Input #1

5

Sample Output #1

5=5

Sample Input #2

6

Sample Output #2

8=2*2*2

Notes

$n \le 48$

见题面 Input 部分

见题面 Output 部分