#O1052. 斐波那契第 n 项

斐波那契第 n 项

题目描述

定义 F1=1F_1 = 1,F2=1F_2 = 1,Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2},求 Fn mod (109+7)F_n \bmod (10^9+7)。

题目类型

矩阵快速幂

输入格式

一行一个整数 nn。

输出格式

一行一个整数,表示 Fn mod (109+7)F_n \bmod (10^9+7)。

样例 #1

样例输入 #1

10

样例输出 #1

55

数据规模与约定

数据范围 说明
1≤n≤10181 \le n \le 10^{18} 项数
  • 用 2×22 \times 2 矩阵快速幂,所有乘法取模,注意 unsigned long long 读入。