#include <iostream>
#include <fstream>

using namespace std;
#define MOD 666013

typedef long long mat[2][2];
typedef mat *pmat;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
int n,k;
mat m,rez;

pmat inm(mat a, mat b)
{
    mat c;
    c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
    c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
    c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
    c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;
    return &c;
}


int main()
{
    m[0][0]=0;
    m[0][1]=1;
    m[1][0]=1;
    m[1][1]=1;
    rez[0][0]=1; rez[1][1]=1;
    fin>>k;
    n=0;
    while (k>0) {
        if (k%2) memcpy(&rez,inm(rez,m),sizeof(rez));
        memcpy(&m,inm(m,m),sizeof(m));
        k=k>>1;
    }
    fout<<rez[1][0]<<"\n";
    fout.close();
    return 0;
}