#CS1722. 斐波那契数

斐波那契数

题目背景

翻译自 CSES-1722 题。

题目描述

斐波那契数可以通过以下公式定义：

你的任务是计算给定 n 时，$F_n$ 的值。

输入格式

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

输出格式

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

样例

10

55

说明/提示

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