#include<iostream>
using namespace std;
#define MAX 32767
int main()
{
long long int exp[MAX]={0};
exp[0]=0;
exp[1]=1;
exp[2]=1;
exp[3]=2;
long long int input;
cin>>input;
for(long long int day=4 ;day<=input;day++)
{
exp[day]=exp[day-1]+exp[day-2];
if((day-1)%3==0)
{
exp[day]--;
}
}
cout<<(exp[input]%100019)<<endl;
return 0;
}