Fibonacci Number

Given a non-negative integer n, compute the n-th Fibonacci number modulo 10⁹+7.

The Fibonacci sequence is defined as follows:

$$F(0)=0,\quad F(1)=1,\quad F(n)=F(n-1)+F(n-2)\quad\text{for } n\ge2.$$

Print the resulting Fibonacci number.

inputFormat

A single line containing one non-negative integer n (0 ≤ n ≤ 10⁵).

outputFormat

Output the n-th Fibonacci number modulo 10⁹+7.

sample

0

0