頁面無法載入？點擊這裡可能會修復。
Placeholder

#6275
子任務

KOI 수열의 수 1s 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分

추가 조건 없음


範例 

3
4


來源

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

需要登入才能撰寫程式碼。