题目描述

请求出斐波那契数列的第$n$项，下标从1开始。

斐波那契数列：1,1,2,3,5…，这个数列从第 3项开始，每一项都等于前两项之和

输入描述

共一行，包含整数$n(1\le n\le 10^5)$。

输出描述

共一行，包含一个整数，表示斐波那契数列的第$n$项。注意，输出结果较大，需要你将结果对$10^9+7$取模。

样例

输入

4

输出

3