题目背景

翻译自 CSES-1722 题。

题目描述

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

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

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

输入格式

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

输出格式

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

样例

10

55

说明/提示

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