题目描述

斐波那契数列定义：F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)。 给定 N，求 F(N) mod 1000000007 的值。

输入格式

一行一个整数 N（0 ≤ N ≤ 100000）。

输出格式

输出 F(N) mod 1000000007。

输入样例

10

输出样例

55