题目描述

相信大家都已经知道斐波那契数列了吧。

斐波那契数列是这样的数列：$f_1=f_2=1,\forall i\geq 3,f_i=f_{i-1}+f_{i-2}$。

给定$n$，求出$f_n\ mod\ 10^9 +7$的值。

输入格式

输入一行一个正整数$n$。

输出格式

输出一行一个整数表示你的答案。

样例输入 #1

10

样例输出 #1

55

说明/提示

对于40%的数据，$1\leq n\leq 10^5$。 对于100%的数据，$1\leq n<2^{63}$。