우리는 재미있는 문자열을 다음과 같이 정의한다.

1. 모든 재미있는 문자열은 알파벳 A, B, C로만 구성되어있다.
2. 모든 재미있는 문자열은 A, BB, CC 중 하나로 끝나야 한다.
3. 모든 재미있는 문자열의 마지막 두 알파벳을 제외한 B 나 C 다음에는 바로 A가 와야 한 다.

정수 N (1<=N<=300,000) 이 주어질 때 길이 N의 재미있는 문자열 개수를 1,000,000로 나눈 나머지로 출력한다.

입력

출력

입출력 예

입력

1

출력 

1

입력

2

출력 

5

추천: likepad