斐波那契数列(升级版)

题目背景

大家都知道,斐波那契数列是满足如下性质的一个数列: - $f(1) = 1 $ - $f(2) = 1$ - $f(n) = f(n-1) + f(n-2)$ ($n ≥ 2$ 且 $n$ 为整数)。

题目描述

请你求出第$n$个斐波那契数列的数mod(或%)$2^{31}$之后的值。并把它分解质因数。

输入输出格式

输入格式


n

输出格式


把第$n$个斐波那契数列的数分解质因数。

输入输出样例

输入样例 #1

5

输出样例 #1

5=5

输入样例 #2

6

输出样例 #2

8=2*2*2

说明

$n \le 48$