#include <bits/stdc++.h>

using namespace std;

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

const int mod = 666013;
const int MAT[3][3] = {{0, 1},
                       {1, 1}};

int SOL[3][3], n;

inline void mult(int A[][3], int B[][3], int C[][3])
{
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;
}

inline void logPow(int p, int M[][3])
{
    int C[3][3], AUX[3][3];

    memcpy(C, MAT, sizeof(MAT));

    M[0][0] = M[1][1] = 1;

    for(int i = 0; (1 << i) <= p; ++i) {
        if(p & (1 << i)) {
            memset(AUX, 0, sizeof(AUX));
            mult(M, C, AUX);
            memcpy(M, AUX, sizeof(AUX));
        }

        memset(AUX, 0, sizeof(AUX));
        mult(C, C, AUX);
        memcpy(C, AUX, sizeof(AUX));

    }
}

int main()
{
    fin >> n;

    logPow(n - 1, SOL);

    fout << SOL[1][1];
}