#include <fstream>

#define MOD 666013

using namespace std;

// inmulteste 2 matrice (folosind conventia cu % MOD) si pune rezultatul in
// dest
// M1 e d1 x d2
// M2 e d2 x d3
// => dest e d1 x d3
void multiply(unsigned long **M1, unsigned long **M2,
                const int d1, const int d2, const int d3,
                unsigned long **dest) {
    for (int row_m1 = 0; row_m1 < d1; ++row_m1) {
        for (int col_m2 = 0; col_m2 < d3; ++col_m2) {
            dest[row_m1][col_m2] = 0UL;

            for (int col = 0; col < d2; ++col) {
                unsigned long add = ((M1[row_m1][col] % MOD)
                                    * (M2[col][col_m2]) % MOD) % MOD;
                dest[row_m1][col_m2] += add;
                dest[row_m1][col_m2] %= MOD;
            }
        }
    }
}

unsigned long **create_matrix(const int rows, const int cols) {
    unsigned long **m = new unsigned long *[rows];
    for (int i = 0; i < rows; i++)
        m[i] = new unsigned long[cols];

    return m;
}

void copy_matrix(const unsigned long **src, unsigned long **dest, const int m,
                const int n) {
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            dest[i][j] = src[i][j];
}

void delete_matrix(unsigned long **m, const int rows) {
    for (int i = 0; i < rows; i++)
        delete[] m[i];
    delete[] m;
}

// ridica m la puterea n si pune rezultatul in dest
void power_matrix(unsigned long **m, const int size, const unsigned long n,
                    unsigned long **dest) {
    if (n == 0UL) {
        for (int i = 0; i < size; ++i)
            for (int j = 0; j < size; ++j)
                dest[i][j] = (i == j) ? 1UL : 0UL;
        return;
    }
    if (n == 1UL) {
        copy_matrix((const unsigned long **) m, dest, size, size);
        return;
    }

    // echivalent cu
    // t = x^(n/2)
    // t = t^2
    unsigned long **temp = create_matrix(size, size);
    power_matrix(m, size, n >> 1, temp);

    // daca n = 2k + 1 (ramura else), temp va fi m^k => temp^2 = m^2k, deci
    // trebuie sa mai inmultesc o data cu m
    if (n % 2 == 0UL) {
        multiply(temp, temp, size, size, size, dest);
    } else {
        unsigned long **m_copy = create_matrix(size, size);
        copy_matrix((const unsigned long **) m, m_copy, size, size);
        unsigned long **temp_sqr = create_matrix(size, size);
        multiply(temp, temp, size, size, size, temp_sqr);
        multiply(temp_sqr, m_copy, size, size, size, dest);
        delete_matrix(m_copy, size);
        delete_matrix(temp_sqr, size);
    }
    delete_matrix(temp, size);
}

unsigned long kfib(const unsigned long k) {
    unsigned long **C = create_matrix(2, 2);
    C[0][0] = 1UL; C[0][1] = 1UL;
    C[1][0] = 1UL; C[1][1] = 0UL;

    unsigned long **F1 = create_matrix(1, 2);
    (*F1)[0] = 1UL, (*F1)[1] = 1UL;

    unsigned long **CK_1 = create_matrix(2, 2);
    power_matrix(C, 2, k - 1, CK_1);

    unsigned long **FK = create_matrix(1, 2);
    multiply(F1, CK_1, 1, 2, 2, FK);

    unsigned long res = (*FK)[1];
    delete_matrix(C, 2);
    delete_matrix(F1, 1);
    delete_matrix(CK_1, 2);
    delete_matrix(FK, 1);

    return res;
}

int main(void) {
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    unsigned long k;
    in >> k;
    out << kfib(k);

    return 0;
}