#include<stdio.h>
long long memo[100000]= {0,1,1};
long long f(int n)
{
if(n<=2) return 1;
if(memo[n]!=0)
{
return memo[n] % 10009;
}
else
{
memo[n]= (f(n-1) + f(n-2)) % 10009;
return memo[n];
}
}
int main()
{
int n;
scanf("%d", &n);
long long int sum=f(n);
printf("%d",f(n));
}