#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,
                int d1, int d2, 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] = 0;
            for (int col = 0; col < d2; ++col)
                dest[row_m1][col_m2]
                    += ((M1[row_m1][col] % MOD) * (M2[col][col_m2] % MOD))
                        % MOD;
        }
}

unsigned long **create_matrix(int rows, 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 delete_matrix(unsigned long **m, 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 matrix_power(unsigned long **m, int size, 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) {
        for (int i = 0; i < size; ++i)
            for (int j = 0; j < size; ++j)
                dest[i][j] = m[i][j];
        return;
    }

    // echivalent cu
    // t = x^(n/2)
    // t = t^2
    unsigned long **temp = create_matrix(size, size);
    matrix_power(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 == 0) {
        multiply(temp, temp, size, size, size, dest);
    } else {
        unsigned long **m_copy = create_matrix(size, size);
        for (int i = 0; i < size; ++i)
            for (int j = 0; j < size; ++j)
                m_copy[i][j] = m[i][j];
        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(unsigned long k) {
    unsigned long **C = create_matrix(2, 2);
    C[0][0] = 1; C[0][1] = 1;
    C[1][0] = 1; C[1][1] = 0;

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

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

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

    unsigned long res = (*FK)[1];
    delete_matrix(C, 2);
    delete_matrix(F0, 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;
}