#include <fstream>

using namespace std;

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

const long long MOD = 666013;

long long k;
long long cst[2][2] = {{0, 1}, {1, 1}};
long long ans[2][2] = {{1, 0}, {0, 1}};
long long tmp[2][2];

inline void multiply(long long a[2][2], long long b[2][2]) {
    tmp[0][0] = ((a[0][0] * b[0][0]) % MOD + (a[0][1] * b[1][0]) % MOD) % MOD;
    tmp[0][1] = ((a[0][0] * b[0][1]) % MOD + (a[0][1] * b[1][1]) % MOD) % MOD;
    tmp[1][0] = ((a[1][0] * b[0][0]) % MOD + (a[1][1] * b[1][0]) % MOD) % MOD;
    tmp[1][1] = ((a[1][0] * b[0][1]) % MOD + (a[1][1] * b[1][1]) % MOD) % MOD;

    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            a[i][j] = tmp[i][j];
}

int main()
{
    fin >> k;
    for (int i = 0; (1 << i) <= (k - 1); ++i) {
        if ((1 << i) & (k - 1))
            multiply(ans, cst);
        multiply(cst, cst);
    }

    long long f = (ans[0][0] % MOD + ans[1][0] % MOD) % MOD;
    fout << f;
    return 0;
}