题目背景

大家都知道，斐波那契数列是满足如下性质的一个数列：

$f(1)=1$

$f(2)=1$

$f(n)=f(n-1)+f(n-2)$（$n\geq2$且$n$为整数）。

题目描述

请你求出第$n$个斐波那契数列的数$\bmod\,2^{31}$之后的值，并把它分解质因数。

输入格式

输入一个正整数$n$。

输出格式

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

样例

5

5=5

6

8=2*2*2

数据范围

$n\le48$

说明

此题数据比洛谷强

来源

洛谷P2626