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