#include <fstream>
#define mod 666013

using namespace std;
ifstream fin ("kfib.in");
ofstream fout("kfib.out");
int n[4][4], m[4][4], s[4][4];
int t,ok,k,a,b,c,x,y,z;

void atrib(int m[4][4], int n[4][4])
{
    int i; int j;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            m[i][j]=n[i][j];
}

void calc(int a[4][4], int b[4][4])
{
    int i,j,l;
    long long aux[4][4];
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        {
            aux[i][j]=0;
            for(l=1;l<=2;l++)
                aux[i][j]=(aux[i][j]+(1LL*a[i][l]*b[l][j])%mod)%mod;
            aux[i][j]%=mod;
        }
     for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            a[i][j]=aux[i][j];
}

void reset()
{
    ok=0;
    n[1][1]=1;n[1][2]=1;
    n[2][1]=1;n[2][2]=0;
    m[1][1]=0;m[1][2]=0;
    m[2][1]=0;m[2][2]=0;
}

int sol()
{
    long long aux=0;
    aux+=(1LL*m[1][1]*1)%mod;
    aux+=(1LL*m[1][2]*1)%mod;
    return aux%mod;
}

int main()
{
    fin>>k;
    k-=2;
    reset();
    while(k>1)
    {
        if(k%2==0)
        {
            calc(n, n);
            k/=2;
        }
        else
            if(k%2==1)
            {
                if(ok==1)
                    calc(m, n);
                else
                {
                    atrib(m, n);
                    ok=1;
                }
                calc(n, n);
                k/=2;
            }
    }
    if(ok==1)
        calc(m, n);
    else
    {
        atrib(m, n);
        ok=1;
    }
    if(k<1)
    {
        if(k==-2)
            fout<<0;
        if(k==-1||k==0)
            fout<<1;
    }
    else
        fout<<sol();
    fout<<"\n";
    fin.close();
    fout.close();
    return 0;
}