/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
char num[50];
int sum = 0, w = 1, i;
scanf("%s",num);
i = 0;
while(num[i] != '\0')
{
i++;
}
while(i--)
{
if(num[i] == '1')
{
sum += w;
}
w *= 2;
}
printf("%d",sum);
}
*/
/*
#include <stdio.h>
int main()
{
int i, save[50],cnt=0;
scanf("%d",&i);
while(i != 0)
{
save[cnt] = i%2;
cnt++;
i = i / 2;
}
for(i = cnt-1; i >=0 ; i--)
{
printf("%d",save[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
/*
#include <stdio.h>
int main()
{
char num[50];
int sum = 0, w = 1, i;
scanf("%s",num);
i = 0;
while(num[i] != '\0')
{
i++;
}
while(i--)
{
if(num[i] == '1')
{
sum += w;
}
w *= 2;
}
printf("%d",sum);
}
*/
/*
#include <stdio.h>
int main()
{
int i, save[50],cnt=0;
scanf("%d",&i);
while(i != 0)
{
save[cnt] = i%2;
cnt++;
i = i / 2;
}
for(i = cnt-1; i >=0 ; i--)
{
printf("%d",save[i]);
}
return 0;
}
*/
/*
int main()
{
char name[30] = {0};
scanf("%s",name);
for(int i = 0; name[i]; i++)
{
printf("%d ",name[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
char name[30] = {0};
int i;
scanf("%s",name);
for(i = 0; name[i]; i++)
{
if(name[i] >= 'A' && name[i] <= 122)
{
name[i] = name[i] - 32;
}
}
printf("%s",name);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n;
printf("n=");
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
if(i%2==1)
{
printf("%d ",i);
}
}
return 0;
}
*/
/*
#include <stdio.h>
void rec(int n)
{
if(n == 0)
{
return;
}
else
{
rec(n/2);
printf("%d",n%2);
}
}
int main()
{
int n;
scanf("%d",&n);
if(n == 0)
{
return 0;
}
else
{
rec(n);
}
}
*/
#include <stdio.h>
int rec(int n)
{
if(n==1 || n ==2)
{
return 1;
}
else
{
return (rec(n-2) + rec(n-1) ) % 10009;
}
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n));
return 0;
}