/*
#include <stdio.h>
int f(int n)
{
if(n==1 || n==2)
{
return 1;
}
return f(n-2)+f(n-1);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n));
}
*/
//#include <stdio.h>
//
//int f(int r, int c)
//{
// if(a==1)
// {
// printf("1");
// return ;
// }
// else if(b==1)
// {0
// f()
// ;
// }
// else if(b==2)
// {
//
// }
//
//
//}
//int main()
//{
// int n;
// scanf("%d", &n);
// f(n, n);
//}
//
/*
int memo[100000] = {0};
int pibo(int k) {
if(k<=2) {
return memo[k] = 1;
}
if(memo[k]!=0) {
return memo[k];
}
return memo[k] = pibo(k-1)%10009 + pibo(k-2)%10009;
}
int main() {
int n;
scanf("%d", &n);
printf("%d", pibo(n)%10009);
}
*
#include <stdio.h>
int memo[51][51]={0};
int f(int r, int c)
{
if(r==1 || c==1)
{
return memo[r][c]=memo[c][r]=1;
}
if(memo[r][c]!=0)
{
return memo[r][c];
}
else
{
return memo[r][c]=memo[c][r]= (f(r-1, c)+f(r, c-1))%1000000000;
}
}
int main()
{
int r, c;
scanf("%d %d", &r, &c);
printf ("%d\n", f(r, c));
return 0;
}
*
#include <stdio.h>
int memo[100001]={0};
int f(int k)
{
if(k==1)
{
return 1;
}
else if(k==2) {
return 2;
}
else if(k==3) {
return 4;
}
if(memo[k]!=0)
{
return memo[k];
}
else
{
return memo[k]= (f(k-3)+f(k-2)+f(k-1))%1000;
}
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n));
}