#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;
}

vector<vector<ull>> multiplyMatrix(vector<vector<ull>> matrixA, vector<vector<ull>> matrixB) {
    /*
     * Matrix A
     */
    ull n = matrixA.size();

    vector<vector<ull>> newMatrix(n, vector<ull>(n));

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

    return newMatrix;
}

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