#include<cstdio>
long long c[3][3],a[3][3],b[3][3],i,j,n,k;
void mult(int n)
    {
    if(n==0)
        return ;
    int i,j,k;
    if(n%2==1)
        {
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                {
                for(k=1;k<=2;k++)
                    {
                    c[i][j]+=a[i][k]*b[k][j];
                    c[i][j]%=666013;
                    }
                }
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                {
                b[i][j]=c[i][j];
                c[i][j]=0;
                }
        mult(n-1);
        }
    else
        {
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                {
                for(k=1;k<=2;k++)
                    {
                    c[i][j]+=a[i][k]*a[k][j];
                    c[i][j]%=666013;
                    }
                }
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                {
                a[i][j]=c[i][j];
                c[i][j]=0;
                }
        mult(n/2);
        }
    }
int main ()
{
freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
a[1][1]=0;
a[1][2]=1;
a[2][1]=1;
a[2][2]=1;
for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
        b[i][j]=a[i][j];
scanf("%lld",&n);
mult(n-3);
printf("%lld",(b[2][1]+b[2][2])%666013);
return 0;
}