n층으로 이루어진 빌딩의 각 층에는 2종류의 엘리베이터가 설치되어있다.

• 엘리베이터 \(A\): 한 번에 \(2\)층씩 올라감

• 엘리베이터 \(B\): 한 번에 \(3\)층씩 올라감

엘사는 1층부터 n층까지 이 두 엘리베이터를 자유롭게 조합해 타고 올라갈 수 있다.

정확히 n층에 도달할 수 있는 경우의 수를 구하여라.

입력 설명

첫째 줄에 정수 n(3 ≤ n ≤ \(10^6\))이 주어진다.

출력 설명

1층에서 n층까지 도달할 수 있는 경우의 수를 1,000,000,007로 나눈 나머지를 출력하라.

예제 입력 1

7

예제 출력 1

2

예제 입력 2

15

예제 출력 2

21

예제 입력 3

12345

예제 출력 3

331327604

Notes

1층부터 7층까지 올라가는 방법은

1 → A이용 → 3 → A이용 → 5 → A이용 → 7

1 → B이용 → 4 → B이용 → 7

이렇게 2가지 경우이다.