#include <iostream>
#include <fstream>

using namespace std;

ifstream f("kfib.in");

ofstream g("kfib.out");

#define MOD 666013

void xmatmod(int a[][2], int b[][2], int rez[][2])
{
    for(int i=0; i<2; i++)for(int j=0; j<2; j++)rez[i][j]=0;
    for(int i=0; i<2; i++)for(int j=0; j<2; j++)for(int k=0; k<2; k++)rez[i][j]+=(1LL*a[i][k]*b[k][j]%MOD);
}

void expmatmod(int a[][2], int p, int rez[][2])
{
    if(p==0)
    {
        for(int i=0; i<2; i++)for(int j=0; j<2; j++){if(i==j)rez[i][j]=1;else rez[i][j]=0;}
        return;
    }
    int half[2][2];
    expmatmod(a,p/2,half);
    xmatmod(half,half,rez);
    if(p%2!=0)
    {
        int tmp[2][2];
        for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp[i][j]=rez[i][j];
        xmatmod(tmp,a,rez);
    }
}

int main()
{
    int k;
    f>>k;
    if(k==0)g<<0;
    else if(k==1||k==2)g<<1;
    else
    {
        int tr[2][2]=
        {
            {1,1},
            {1,0}
        },rez[2][2],fibo=0;
        expmatmod(tr,k-2,rez);
        for(int i=0;i<2;i++)fibo+=(rez[i][0]);
        g<<fibo;
    }
    return 0;
}