题目描述

求斐波那契数列第 $n$ 项对 $10^9+7$ 取模的结果，其中

输入格式

一行一个整数 $n$。

输出格式

一个整数，表示 $f_n \bmod (10^9+7)$。

输入输出样例 #1

输入 #1

10

输出 #1

55

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^{18}$。