#include <fstream>
#include <cstring>

using namespace std;

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

const int MOD = 666013;

int cst[3][3], fib[3][3];
int K;

inline void writeMat(int a[3][3]) {
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j)
            fout << a[i][j] << ' ';
        fout << '\n';
    }
    fout << '\n';
}

inline void initMatrix() {
    fib[0][0] = fib[0][1] = 1;
    cst[0][1] = cst[1][0] = cst[1][1] = 1;
}

inline void multiplyMatrix(int a[3][3], int b[3][3]) {
    int c[3][3];
    memset(c, 0, sizeof c);
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            c[i][j] = (1LL * a[i][0] * b[0][j] + 1LL * a[i][1] * b[j][1]) % MOD;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            a[i][j] = c[i][j];
   // writeMat(a);
}

inline void logPower(int k) {
    for (int i = 0; (1LL << i) <= k; ++i) {
        if ((1LL << i) & k)
            multiplyMatrix(fib, cst);
        multiplyMatrix(cst, cst);
    }
}

int main()
{
    fin >> K;
    initMatrix();
    logPower(K - 1);
    fout << fib[0][0];
    return 0;
}