You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

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

Description

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

  在很多情况下，假定 $F_{n}=F_{n-1} + F_{n-2}$ 对 所有整数 $n$ 成立，是很方便的

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

Format

Input

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

Output

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

Samples

5

5

-2

-1

Notes

  【思考】能否用 $F_n$ 表示 $F_{-n}$？