#include <iostream>
#include <vector>
#include <fstream>

#define MOD 666013
#define ull unsigned long long
#define Z {{0, 1}, {1, 1}}
#define identity {{1, 0}, {0, 1}}

using namespace std;

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

void printMatrix(vector<vector<ull>> matrix);
vector<vector<ull>> multiplyMatrix(vector<vector<ull>> matrixA, vector<vector<ull>> matrixB);


/*
 * (F(0), F(1))
 * (F(1), F(2))
 * F(0) = 0, F(1) = 1, F(2) = 1
 */
vector<vector<ull>> exp(vector<vector<ull>> matrix, unsigned p) {
    if (p == 0)
        return identity;

    vector<vector<ull>> matrixSq = multiplyMatrix(matrix, matrix);

    if (p % 2)
        return multiplyMatrix(matrix, exp(matrixSq, (p - 1) / 2));

    return exp(matrixSq, p / 2);
}

int main() {
    unsigned K;
    fin >> K;

    fout << exp(Z, K)[0][1];

    return 0;
}

// tot row ul inmultit cu tot column ul
// A (m x n) x B (n x p) = M (m x p)
vector<vector<ull>> multiplyMatrix(vector<vector<ull>> matrixA, vector<vector<ull>> matrixB) {
    /*
     * Matrix A
     */
    ull matrixARows = matrixA.size(), matrixAColumns = matrixA[0].size();

    /*
     * Matrix B
     */
    ull matrixBRows = matrixB.size(), matrixBColumns = matrixB[0].size();

    vector<vector<ull>> newMatrix(matrixARows, vector<ull>(matrixBColumns));

    // we know that matrixAColumns = matrixBRows
    // meaning then size of newMatrix = matrixARows x matrixBColumns

    for (unsigned i =  0; i < matrixARows; ++i)
        for (unsigned j = 0; j < matrixAColumns; ++j) {
            unsigned sum = 0;

            for (unsigned k = 0; k < matrixBRows; ++k)
                sum += (matrixA[i][k] % MOD * matrixB[k][j] % MOD) % MOD;

            newMatrix[i][j] = sum;
        }

    return newMatrix;
}

void printMatrix(vector<vector<ull>> matrix) {
    for (vector<ull> row : matrix) {
        for (ull elem : row) {
            cout << elem << ' ';
        }
        cout << '\n';
    }
}