#include <iostream>

using namespace std;
const int NMAX=100000000;
int d[NMAX+1];
int v[]={1,2,3};
int main()
{
    int i,j,n;
    d[0]=1;
    for(i=0;i<3;i++)
        for(j=v[i];j<=NMAX;j++)
        {
            d[j]=d[j]+d[j-v[i]];
            if(d[j]>1000000)
                d[j]-=1000000;

        }
    cin>>n;
    cout<<d[n];

    return 0;
}