Description

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

f(1)=1

f(2)=1

f(n)=f(n−1)+f(n−2) (n≥2 且 n 为整数)。 请你求出第 n 个斐波那契数列的数mod（或%）$2^{31}$之后的值。并把它分解质因数。

Input Format

n

Output Format

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

6​

8=2*2*2​

Hint

n ≤ 48