20250627
/*#include <stdio.h>
#define LLD long long int
#define P printf
LLD mul(LLD n,LLD k,LLD m)
{
if(k==0)
{
return m;
}
return mul(n,k-1,m*n);
}
int main()
{
LLD n,k,m=1;
scanf("%lld %lld",&n,&k);
if(n==1||k==0||n==-1&&k%2==0)
{
printf("1");
return 0;
}
if(n==-1&&k%2==1)
{
printf("-1");
return 0;
}
n=mul(n,k,m);
printf("%lld",n);
return 0;
}
*/
/*
#define LLD long long int
#define P printf
#include <stdio.h>
LLD cha(LLD n,LLD m)
{
if(n<10)
{
m=m+n;
return m;
}
return cha(n/10,m+n%10);
}
int main()
{
LLD n,m=0;
scanf("%lld",&n);
n=cha(n,m);
printf("%lld",n);
return 0;
}
*/
#include <stdio.h>
int m[100001]={0,1,1,2, };
int cha(int n,int c,int l)
{
if(c==n-1)
{
return m[l-1];
}
m[l]=(m[l-3]+m[l-2]+m[l-1])%1000; //피보나치 수열 만드는 방법: 피보나치 수열 전 3개 모두 더하기
printf("\n%d",m[l]);
return cha(n,c+1,l+1);
}
int main()
{
int n,c=1,l=4;
scanf("%d",&n);
if(n==0)
{
printf("0");
return 0;
}
if(n==1||n==2)
{
printf("1");
return 0;
}
if(n==3)
{
printf("2");
return 0;
}
n=cha(n,c,l);
n=n%1000;
printf("\n\n%d",n);
return 0;
}