memo = [-1] * 10007

def fibo(N):
    if N == 1 or N == 2:
        return 1
    if memo[N] != -1:
        return memo[N]
    memo[N] = (fibo(N-1) + fibo(N-2)) % 10009
    return memo[N]

N = int(input())
print(fibo(N))