#include<cstdio>
long long mb[6][6],ma[6][6],mc[6][6];
const int mo=666013;
int calc(int n)
{
    int i,j,x;
    if(n>1)
    {
        calc(n/2);
        for(i=1; i<=2; i++)
            for(j=1; j<=2; j++)
                for(x=1; x<=2; x++)
                    mc[i][x]=(mc[i][x]+ma[i][j]*ma[j][x])%mo;
        for(i=1; i<=2; i++)
            for(j=1; j<=2; j++)
            {
                ma[i][j]=mc[i][j];
                mc[i][j]=0;
            }
        if(n%2==1)
        {
            for(i=1; i<=2; i++)
                for(j=1; j<=2; j++)
                    for(x=1; x<=2; x++)
                        mc[i][x]=(mc[i][x]+ma[i][j]*mb[j][x])%mo;
            for(i=1; i<=2; i++)
                for(j=1; j<=2; j++)
                {
                    ma[i][j]=mc[i][j];
                    mc[i][j]=0;
                }
        }
    }
    else
    {
        ma[1][2]=ma[2][1]=ma[2][2]=1;
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%d",&n);
    mb[1][2]=mb[2][1]=mb[2][2]=1;
    calc(n);
    printf("%d\n",ma[2][1]);
    return 0;
}