//#include <iostream>
//
//using namespace std;
//
//int main()
//{
// int num,arr1[30][30]={},arr2[30][30]={};
// for(int i=1; i<=25; i++)
// {
// for(int j=1; j<=25; j++)
// {
// cin>>num;
// arr1[i][j]=num;
// }
// }
// for(int i=1; i<=25; i++)
// {
// for(int j=1; j<=25; j++)
// {
// if(arr1[i][j]==0)
// {
// num=0;
// for(int a=i-1; a<=i+1; a++)
// {
// for(int b=j-1; b<=j+1; b++)
// {
// if(arr1[a][b]==1)
// {
// num++;
// }
// }
// }
// if(num==3)
// {
// arr2[i][j]=1;
// }
// else
// arr2[i][j]=0;
// }
// else if(arr1[i][j]==1)
// {
// num=0;
// for(int a=i-1; a<=i+1; a++)
// {
// for(int b=j-1; b<=j+1; b++)
// {
// if(arr1[a][b]==1)
// {
// num++;
// }
// }
// }
// if(num-1<=1 || num-1>=4)
// {
// arr2[i][j]=0;
// }
// else if(num-1==2 || num-1==3)
// {
// arr2[i][j]=1;
// }
// else
// arr2[i][j]=1;
// }
// }
// }
//
// for(int i=1; i<=25; i++)
// {
// for(int j=1; j<=25; j++)
// {
// cout<<arr2[i][j]<<' ';
// }
// cout<<endl;
// }
//}
/*
#include <iostream>
using namespace std;
int main()
{
int num,a,b,x,y,z,k,arr1[180][180]= { },arr2[180][180]= { };
cin>>a>>b;
cin>>x>>y>>z;
for(int i=1; i<=a; i++)
{
for(int j=1; j<=b; j++)
{
cin>>arr1[i][j];
}
}
cin>>k;
while(k!=0)
{
for(int i=1; i<=a; i++)
{
for(int j=1; j<=b; j++)
{
num=0;
for(int a=i-1; a<=i+1; a++)
{
for(int b=j-1; b<=j+1; b++)
{
num+=arr1[a][b];
}
}
if(arr1[i][j]==1)
{
num--;
if(num>=y && num<z)
{
arr2[i][j]=1;
}
else if(num>=z)
{
arr2[i][j]=0;
}
}
else if(!arr1[i][j])
{
if(num==x)
arr2[i][j]=1;
}
}
}
for(int i=1; i<=a; i++)
{
for(int j=1; j<=b; j++)
{
arr1[i][j]=arr2[i][j];
arr2[i][j] = 0;
}
}
k--;
}
for(int i=1; i<=a; i++)
{
for(int j=1; j<=b; j++)
{
cout<<arr1[i][j]<<' ';
}
cout<<endl;
}
}
*/
/*
#include <stdio.h>
int main()
{
int n,m,num,arr[100001]={};
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&num);
arr[num]=1;
}
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
scanf("%d",&num);
if(arr[num]==1)
printf("1 ");
else
printf("0 ");
}
}
*/
#include <stdio.h>
int arr[1500000]={0, 1, 1, 2, 3, 5};
int f(int n)
{
if(n<=2){
return arr[n]=1;
}
if(arr[n])
{
return arr[n];
}
return arr[n] = (f(n-2)+f(n-1))%10009;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d" , f(n));
}