import sys
input = sys.stdin.readline
n = int(input())

L = [0,1]
a = 1000000

if n >= 2:
    for i in range(n-1):
        L.append(L[i]+L[i+1])
    print(L[-1]%a)

elif n == 1:
    print(1%a)

elif n == 0:
    print(0%a)