#FIRST1. 【常规】斐波那契数列(简单版)

【常规】斐波那契数列(简单版)

Background

  斐波那契数列是一种大家所熟知的数列

Description

  对于斐波那契数列,我们知道有

$$F_0=0, F_1=1, F_n = F_{n-1} + F_{n-2} \ \ (n \geq 2) $$

  在很多情况下,假定 Fn=Fn1+Fn2F_{n}=F_{n-1} + F_{n-2}所有整数 nn 成立,是很方便的

  对于给出的 nn,请求出 FnF_n 的值。这个数可能很大,因此你只需要输出 Fnmod109+7F_n \mod 10^9 + 7 的值

Format

Input

  第一行一个整数 n (105n105)n \ (-10^{5} \leq n \leq 10^{5}),代表所求斐波那契数列的项数

Output

  第一行一个整数,代表 Fnmod109+7F_n \mod 10^9 + 7 的值

Samples

5
5
-2
-1

Notes

  【思考】能否用 FnF_n 表示 FnF_{-n}