#include <bits/stdc++.h>

using namespace std;

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

typedef int mat2x2[2][2];

const int MOD = 666013;

void mat_mul(mat2x2 a, mat2x2 b) {
    mat2x2 cpy;
    memcpy(cpy, a, sizeof(mat2x2));
    cpy[0][0] = (1ll * a[0][0] * b[0][0] + 1ll * a[0][1] * b[1][0]) % MOD;
    cpy[0][1] = (1ll * a[0][0] * b[0][1] + 1ll * a[0][1] * b[1][1]) % MOD;
    cpy[1][0] = (1ll * a[1][0] * b[0][0] + 1ll * a[1][1] * b[1][0]) % MOD;
    cpy[1][1] = (1ll * a[1][0] * b[0][1] + 1ll * a[1][1] * b[1][1]) % MOD;
    memcpy(a, cpy, sizeof(mat2x2));
}

int fib(int n) {
    mat2x2 dp1 = {{0, 1}, {1, 1}};
    mat2x2 mat = {{0, 1}, {1, 1}};

    vector<bool> b;
    while (n != 1) {
        b.push_back(n & 1);
        n >>= 1;
    }

    for (int i = b.size() - 1; i >= 0; i--) {
        mat_mul(mat, mat);
        if (b[i])
            mat_mul(mat, dp1);
    }

    return mat[0][1];
}

int main() {
    int n;
    fin >> n;
    fout << fib(n);
    return 0;
}