#P2626. 斐波那契数列(升级版)

斐波那契数列(升级版)

题目背景

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

  • f(1)=1f(1) = 1
  • f(2)=1f(2) = 1
  • f(n)=f(n1)+f(n2)f(n) = f(n-1) + f(n-2)n>2n > 2nn 为整数)。

题目描述

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

输入格式

输入一个正整数 nn

输出格式

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

5
5=5
6
8=2*2*2

提示

n48n \le 48