#include <cstdio>
#define MOD 666013
long long mat1[3][3],mat2[3][3],tmp[3][3],tmp2[3][3];
int n,pt;
void pat()
{
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            tmp2[i][j]=mat2[i][j];
            tmp[i][j]=mat2[i][j];
            mat2[i][j]=0;
        }
    }
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                mat2[i][j]+=(tmp[i][k]*tmp2[k][j]);
                mat2[i][j]%=MOD;
            }
        }
    }
}
void inmultire()
{
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++) tmp[i][j]=0;
    }
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                tmp[i][j]+=(mat1[i][k]*mat2[k][j]);
                tmp[i][j]%=MOD;
            }
        }
    }
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++) mat1[i][j]=tmp[i][j];
    }
}
void gas()
{
    int temp=n;
    while(temp!=0)
    {
        pt++;
        temp>>=1;
    }
    pt--;
}
void inm()
{
    bool as=n%2;
    for(int i=1;i<=pt;i++)
    {
        pat();
        if((n&(1<<i)))
        {
            if(as==0)
            {
                as=1;
                for(int i=1;i<=2;i++)
                {
                    for(int j=1;j<=2;j++) mat1[i][j]=mat2[i][j];
                }
            }
            else
            {
                inmultire();
            }
        }
    }
}
int main()
{
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);
    scanf("%d",&n);
    n-=2;
    gas();
    mat1[2][1]=1;
    mat1[1][2]=1;
    mat1[2][2]=1;
    mat2[2][1]=1;
    mat2[1][2]=1;
    mat2[2][2]=1;
    inm();
    long long int nr=mat1[1][2]+mat1[2][2];
    nr%=666013;
    printf("%lld\n",nr);
}