/*
#include<stdio.h>
int memo[1000000] ={0};
int pibo(int n) {
if(n==1 || n==2) {
return memo[n] = 1;
}
if(memo[n]!=0) {
return memo[n]%10009;
}
else{
return memo[n] = (pibo(n-1) + pibo(n-2))%10009;
}
}
int main() {
int n;
scanf("%d", &n);
printf("%d", pibo(n)%10009);
}
*/
/*
#include <stdio.h>
int memo[100][100]= {0};
int rec(int r, int c)
{
if(r==1 || c==1)
{
return memo[r][c]=1;
}
if(memo[r][c]!=0)
{
return memo[r][c];
}
return memo[r][c] = (rec(r,c-1) + rec(r-1,c))%100000000;
}
int main()
{
int r,c;
scanf("%d %d",&r, &c);
printf("%d",rec(r,c));
}
*/#include <stdio.h>
int memo[100001]= {0};
int rec(int n)
{
if(memo[n]<=3)
{
return memo[n];
}
if(n==1 || n==2)
{
return memo[n]=n;
}
else if(n==3)
{
return memo[n]=4;
}
return memo[n] = (rec(n-3)+rec(n-2)+rec(n-1))%1000;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n));
}