#include <fstream>

using namespace std;

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

const int MOD = 666013;

long long mat[2][2] = {{0, 1}, {1, 1}}; // matricea constanta
long long ans[2][2] = {{1, 0}, {0, 1}}; // matricea unitate
long long tmp[2][2];
int k;

inline void multiplyMatrix(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;
    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))
            multiplyMatrix(ans, mat);
        multiplyMatrix(mat, mat);
    }

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