#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int a[2][2]= {{0,1},{1,1}},an[2][2]= {{0,1},{1,1}};
void matrixmult(int x[2][2],int y[2][2],int z[2][2])
{int i,j,k,m1[2][2],m2[2][2];
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            m1[i][j]=x[i][j];
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            m2[i][j]=y[i][j];
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            z[i][j]=0;
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            for (k=0;k<2;k++)
            {
                z[i][j]+=m1[i][k]*m2[k][j];
                if (z[i][j]>666013) z[i][j]=z[i][j]%666013;
            }
}
void pow(int n)
{
    if (n<=1)return;
    if (n%2==0)pow(n/2),matrixmult(an,an,an);
    else pow(n-1),matrixmult(an,a,an);
}

int main()
{int k,ans;

    f>>k;
    if (k<2)g<<1;
    else pow(k-2),ans=an[0][1]+an[1][1],ans%=666013,g<<ans;
}