01타일

길이가 N인 이진 문자열(0과 1로만 이루어진) 중 "00"이 연속으로 나타나지 않는 문자열의 개수를 구하라.

예를 들어 N=2이면 01, 10, 11로 3가지이다. (00은 제외)

이 점화식은 피보나치 수열과 동일하다: dp[n] = dp[n-1] + dp[n-2].

입력

첫째 줄에 N이 주어진다.

• 1 ≤ N ≤ 1,000,000

출력

조건을 만족하는 문자열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력 1

5

예제 출력 1

13