#include <fstream>

using namespace std;

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

typedef long long i64;

const int mod=666013;
i64 v[2], m[2][2], v2[2], m2[2][2], m3[2][2];

int main () {
    i64 n;
    fin>>n;

    if (n==0) {
        fout<<"0\n";
    } else {
        m[0][0]=0;
        m[0][1]=1;
        m[1][0]=1;
        m[1][1]=1;
        v[0]=0;
        v[1]=1;
        m2[0][0]=1;
        m2[0][1]=0;
        m2[1][0]=0;
        m2[1][1]=1;
        for (int i=1; i<=n-1; i*=2) {
            if (((n-1)&i)!=0) {
                for (int j=0; j<2; j++) {
                    for (int k=0; k<2; k++) {
                        m3[j][k]=0;
                        for (int l=0; l<2; l++) {
                            m3[j][k]+=m2[j][l]*m[l][k];
                        }
                    }
                }
                for (int j=0; j<2; j++) {
                    for (int k=0; k<2; k++) {
                        m2[j][k]=m3[j][k]%mod;
                    }
                 }
            }
            for (int j=0; j<2; j++) {
                for (int k=0; k<2; k++) {
                    m3[j][k]=0;
                    for (int l=0; l<2; l++) {
                        m3[j][k]+=m[j][l]*m[l][k];
                    }
                }
            }
            for (int j=0; j<2; j++) {
                for (int k=0; k<2; k++) {
                    m[j][k]=m3[j][k]%mod;
                }
            }
        }
        for (int k=0; k<2; k++) {
            v2[k]=0;
            for (int l=0; l<2; l++) {
                v2[k]+=v[l]*m2[l][k];
            }
        }
        fout<<v2[1]%mod<<"\n";
    }

    return 0;
}