#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD=666013;

long long mat[5][5];
long long sol[5][5];
long long aux[5][5];
int n;

void prod(int a[5][5],int b[5][5],int c[5][5])
{
    c[1][1]=a[1][1]*b[1][1]+a[1][2]*b[2][1];
    c[1][2]=a[1][1]*b[1][2]+a[1][2]*b[2][2];

    c[2][1]=a[2][1]*b[1][1]+a[2][2]*b[2][1];
    c[2][2]=a[2][1]*b[1][2]+a[2][2]*b[2][2];
}
void expow(int x)
{
    sol[1][1]=sol[2][2]=1;
    while(x>0)
    {
        if(x%2==1)
        {
            aux[1][1]=(mat[1][1]*sol[1][1]+mat[1][2]*sol[2][1])%MOD;
            aux[1][2]=(mat[1][1]*sol[1][2]+mat[1][2]*sol[2][2])%MOD;
            aux[2][1]=(mat[2][1]*sol[1][1]+mat[2][2]*sol[2][1])%MOD;
            aux[2][2]=(mat[2][1]*sol[1][2]+mat[2][2]*sol[2][2])%MOD;

            sol[1][1]=aux[1][1];
            sol[1][2]=aux[1][2];

            sol[2][1]=aux[2][1];
            sol[2][2]=aux[2][2];
        }
        x/=2;
        /// mat*=mat
        aux[1][1]=(mat[1][1]*mat[1][1]+mat[1][2]*mat[2][1])%MOD;
        aux[1][2]=(mat[1][1]*mat[1][2]+mat[1][2]*mat[2][2])%MOD;
        aux[2][1]=(mat[2][1]*mat[1][1]+mat[2][2]*mat[2][1])%MOD;
        aux[2][2]=(mat[2][1]*mat[1][2]+mat[2][2]*mat[2][2])%MOD;

        mat[1][1]=aux[1][1];
        mat[1][2]=aux[1][2];

        mat[2][1]=aux[2][1];
        mat[2][2]=aux[2][2];
    }
}

int main()
{
    fin>>n;
    mat[1][1]=0;mat[1][2]=mat[2][1]=mat[2][2]=1;
  ///  sol[1][1]=0;sol[1][2]=sol[2][1]=sol[2][2]=1;
    expow(n-1);
    fout<<sol[2][2];
    return 0;
}