문제

피보나치 함수 $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 1\,000\,000)$ 이 주어진다.

출력

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

예제 입력 1

6

예제 출력 1

8

예제 입력 2

1000000

예제 출력 2

918091266

힌트

모듈러 연산의 분배법칙을 활용하여 연산 속도를 향상시킬 수 있다.

단, 모듈러 연산에서 나눗셈의 분배법칙은 성립하지 않는다.