Informatica Online Judge

  귀갓길 [2298 / 08FA]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 5   Total Tried : 6


The Champion of this Problem (C++) : gs16109 - ms / 479byte
My Best Submission (C++) : N/A

[34th 조현우]

Background

전체 귀가 날에 버스를 놓친 현우는 학교에서 집까지 걸어가려고 한다.

학교에서 집까지 가는 길은 (0, 0)부터 (n, n)까지의 교차로를 가진 격자로 구성되어 있다.

학교는 (0, 0)에, 현우의 집은 (n, n)에 위치해 있다.

키가 큰 현우는 한 번에 2칸 떨어진 곳으로만 움직일 수 있다.

즉, 현재 현우의 위치가 (x, y)인 경우, 다음 위치로 가능한 곳은 (x+2, y), (x+1, y+1), (x, y+2) 3가지이다.

현재 현우는 어디로 가야 할 지 몰라서 아무것도 못하고 있다.

학교에서 집까지 갈 수 있는 경로의 수를 구하는 프로그램을 작성하여 현우를 도와주자.

단, 경로의 수가 너무 많으므로 1000003으로 나눈 나머지를 구하도록 하자.

Input

첫째 줄에 n이 주어진다. (0 < n <= 10^18)

Output

경로의 수를 1000003으로 나눈 나머지를 출력한다.

IO Example

입력
2

출력
3

입력
10000

출력
673083

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]