#include <bits/stdc++.h>

using namespace std;

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

const int rem=666013;

int mat[2][2],res[2][2],kf,aux[2][2];

void matexp (int q[][2], int qq[][2], int qqq[][2]){
    for(int i=0;i<=1;++i)
        for(int j=0;j<=1;++j)
            for(int k=0;k<=1;++k)
                qqq[i][j]=(qqq[i][j]+1LL*q[i][k]*qq[k][j])%rem;
}

void logexp(int q, int m[][2]){
    //int aux[2][2];
    res[0][0]=res[0][1]=1;
    for(int i=0;(1<<i)<=q;++i){
        if(q&(1<<i)){
            memset(aux,0,sizeof aux);
            matexp(res,m,aux);
            memcpy(res,aux,sizeof aux);
        }
        memset(aux,0,sizeof aux);
        matexp(m,m,aux);
        memcpy(m,aux,sizeof aux);
    }
}

int main()
{
    fin>>kf;
    mat[0][1]=mat[1][0]=mat[1][1]=1;
    logexp(kf-2,mat);
    fout<<res[0][1];
    return 0;
}