#include <fstream>
#include <algorithm>
using namespace std;
long long a[5][5],b[5][5],c[5][5],d[5][5],sol[5][5];
int main()
{
    long long n,m,i,j,k,l,p,pas;
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    in>>n;
    p=n;
    sol[1][1]=1;
    sol[1][2]=0;
    sol[2][1]=0;
    sol[2][2]=1;
    b[1][1]=1;
    b[1][2]=1;
    b[2][1]=1;
    b[2][2]=0;
    while(p>0)
    {
        if(p%2==1)
        {
            for(j=1;j<=2;j++)
            {
                for(k=1;k<=2;k++)
                {
                    for(l=1;l<=2;l++)
                    {
                        a[j][k]=a[j][k]+sol[j][l]*b[l][k];
                        if(a[j][k]>666013)
                            a[j][k]%=666013;
                    }
                }
            }
            p--;
            for(i=1;i<=2;i++)
            {
                for(j=1;j<=2;j++)
                {
                    sol[i][j]=a[i][j];
                    a[i][j]=0;
                }
            }
        }
        if(p)
        {
            for(i=1;i<=2;i++)
            {
                for(j=1;j<=2;j++)
                {
                    d[i][j]=b[i][j];
                }
            }
            for(j=1;j<=2;j++)
            {
                for(k=1;k<=2;k++)
                {
                    for(l=1;l<=2;l++)
                    {
                        c[j][k]=c[j][k]+b[j][l]*d[l][k];
                        if(c[j][k]>666013)
                            c[j][k]%=666013;
                    }
                }
            }
            p/=2;
            for(i=1;i<=2;i++)
            {
                for(j=1;j<=2;j++)
                {
                    b[i][j]=c[i][j];
                    c[i][j]=0;
                }
            }
        }
    }
    out<<sol[1][2]%666013;
    return 0;
}