문제

피보나치 함수 $f$는 아래와 같이 정의된다.

$f(0)=0,\quad f(1)=1$

$f(x)=f(x-1)+f(x-2)\ \quad (x\ge2)$

이때, $f(n)$ 의 값을 출력하는 프로그램을 작성해보자.

수가 매우 커질 수 있으므로 소수 $1\,000\,000\,007$로 나눈 나머지를 출력하자.

입력

첫째 줄에 $n(0\le n \le 10^{18})$ 이 주어진다.

출력

$f(n)$ 의 값 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

예제 입력 1

6

예제 출력 1

8

예제 입력 2

100000000000000000

예제 출력 2

469857088