链接: https://cses.fi/problemset/task/1722

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

斐波那契数列定义如下：

• $F_0=0$
• $F_1=1$
• $F_n = F_{n-2}+F_{n-1}$

你的任务是计算给定 $n$ 对应的 $F_n$ 的值。

输入

唯一的输入行包含一个整数 $n$。

输出

输出 $F_n$ 对 $10^9+7$ 取模的值。

数据范围

$0 \le n \le 10^{18}$

样例输入

10

样例输出

55