#include <fstream>
#include <cstring>
#define MOD 666013
#define D 3

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

int n;
long long Fib[D][D];

void MatrixMultipication (long long A[D][D], long long B[D][D], long long C[D][D]) {

    long long aux[D][D];
    memset(aux,0,sizeof(aux));

    for (int i=1; i<=2; ++i)
        for (int j=1; j<=2; ++j) {

            long long S=0;
            for (int k=1; k<=2; ++k) {

                S += 1LL * A[i][k] * B[k][j];

                aux[i][j]=S%MOD;
            }
        }

    memcpy(C,aux,sizeof(aux));
}

void MatrixPower(long long A[D][D],int k) {

    long long aux[D][D];
    memset(aux,0,sizeof(aux));

    for (int i=1; i<=2; ++i) aux[i][i]=1;

    while (k>1) {

        if (k%2==0) {

            k=k/2;
            MatrixMultipication(A,A,A);
        }
        else
        {
            --k;
            MatrixMultipication(aux,A,aux);
        }
    }

    MatrixMultipication(aux,A,A);
}

void Solve() {

    Fib[1][1]=0; Fib[1][2]=1;
    Fib[2][1]=1; Fib[2][2]=1;

    MatrixPower(Fib,n-1);

    g<<Fib[2][2]<<'\n';
}

int main() {

    f>>n;

    Solve();

    f.close();
    g.close();
    return 0;
}