#include<bits/stdc++.h>
#define mod 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long mat[4][4],rez[4][4];

void init()
{
    mat[1][2]=1;
    mat[2][2]=1;
    mat[2][1]=1;
    rez[1][1]=rez[2][2]=1;
}
int k;

void mult(long long a[][4],long long b[][4])
{
    long long copie[4][4];
    memset(copie,0,sizeof(copie));
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
        for(int l=1;l<=2;++l)
        copie[i][j]=(copie[i][j]+a[i][l]*b[l][j]%mod)%mod;
     for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            a[i][j]=copie[i][j]%mod;
}

void inm(int k)
{
    while(k)
    {
        if(k&1)
        {
            mult(rez,mat);
        }
        mult(mat,mat);

        k>>=1;
    }
}

int main()
{
    f>>k;
    k--;
    init();
    if(k==0)
        g<<0;
    else
    {
        inm(k);
        g<<rez[2][2];
    }
}