#슬슬 시작해볼까나
#약수의 개수 구하기
# n = int(input())
# def f(n):
# sum = 0
# for k in range(1, n+1):
# if n%k == 0:
# sum += 1
# print(sum)
# f(n)
#뒤집어 리턴하기
# n = input()
# def f(n):
# n = list(n)
# n.reverse()
# print(''.join(n))
# f(n)
#두 수의 최대공약수
# a, b = map(int, input().split())
# def f(a, b):
# g = []
# ka = []
# lb = []
# for k in range(1, a+1):
# if a%k == 0:
# ka.append(k)
# for l in range(1, b+1):
# if b%l == 0:
# lb.append(l)
# for i in ka:
# for j in lb:
# if i == j:
# g.append(i)
# g.sort(reverse=True)
# print(g[0])
# f(a, b)
# 최소공배수 되긴하는데 시간초과가 된다.
# a, b = map(int, input().split())
#
#
# def f(a, b):
# g = []
# ka = []
# lb = []
# for k in range(1, a+1):
# if a % k == 0:
# ka.append(k)
# for l in range(1, b+1):
# if b % l == 0:
# lb.append(l)
# for i in ka:
# for j in lb:
# if i == j:
# g.append(i)
# g.sort(reverse=True)
# G = g[0]*a//g[0]*b//g[0]
# print(G)
#
#
# f(a, b)
# 두 수의 최소공배수
# a, b = map(int, input().split())
# def gcd(a, b):
# if a>= b:
# r = a % b
# if r == 0:
# return b
# else:
# return gcd(r, b)
# else:
# return gcd(b, a)
#
#
# def lcm(a, b):
# c = gcd(a, b)
# return c*a//c*b//c
#
#
# print(lcm(a, b))
#재귀 함수
# n = int(input())
# def rec(k):
# if k==0:
# return
# # rec(k-1)
# print(k)
# rec(k-1)
# rec(n)
#
# a, b = map(int, input().split())
# def rec(a, b):
# if a % 2 == 1:
# print(a, end=' ')
# if a == b:
# return
# rec(a+1, b)
# rec(a, b)
#
# import sys
# sys.setrecursionlimit(10**8)
#
# n = int(input())
# def rec(k):
# if k==1:
# return 1
# return k + rec(k-1)
# print(rec(n))
# n = int(input())
# def rec(k):
# if k == 1:
# return 1
# return k * rec(k-1)
# print(rec(n))
#
# import sys
# sys.setrecursionlimit(10**8)
#
# n = int(input())
# def rec(k):
# if k == 1 or k==2:
# return 1
# else:
# return rec(k-1) + rec(k-2)
# print(rec(n))
import sys
sys.setrecursionlimit(10**9)
n = int(input())
def rec(k):
if k == 1 or k == 2:
return 1
else:
return rec(k-1) + rec(k-2)
rec(k) % 10009
print(rec(n))