페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6275
서브태스크

KOI 수열의 수 1초 32MB

문제

양의 정수 N에 대하여, 1부터 N까지의 정수들 중에서 다음 조건을 모두 만족하도록 하나 이상을 뽑아 나열한 것을 KOI수열이라고 하자.

  1. 두 번째 수부터는 바로 이전의 수보다 반드시 커야한다.

  2. 홀수 번째 위치하는 수는 반드시 홀수여야 하고, 짝수 번째 위치하는 수는 반드시 짝수이어야 한다.

예를 들어, N=3일 때 KOI수열은 다음과 같은 네 가지가 있다: [1], [3], [1,2], [1,2,3]


입력

첫 줄에 정수 N이 주어진다. (1 \le N \le 100,000)


출력

첫 줄에 KOI수열의 개수를 100,003로 나눈 나머지를 출력한다.


부분문제

번호 점수 조건
#130점

N \le 15

#270점

추가 조건 없음


예제1

입력
3
출력
4

태그

출처

KOI 시도예선 수학 2013 중고등부 11,12번

역링크