#include <fstream>
#include <string>
#include <vector>

using namespace std;


typedef unsigned long long ULL;


template <typename type>
using Matrix = vector<vector<type>>;


string const inFile = "kfib.in";
string const outFile = "kfib.out";

unsigned const MOD = 666013;


ifstream Read(inFile);
ofstream Write(outFile);


template <typename type>
void InitMatrix(Matrix<type> &matrix) {
    matrix.resize(2, vector<type>(2));

    matrix[0][0] = 0;
    matrix[0][1] = 1;
    matrix[1][0] = 1;
    matrix[1][1] = 1;
}

template <typename type>
Matrix<type> MatrixMultiply(Matrix<type> &matrix1, Matrix<type> &matrix2) {
    Matrix<type> result(matrix1.size(), vector<type>(matrix2[0].size()));
    unsigned i, j, k;

    for (i = 0; i < result.size(); ++i)
    for (j = 0; j < result[0].size(); ++j) {
        result[i][j] = 0;

        for (k = 0; k < matrix2.size(); ++k) {
            result[i][j] += ULL(ULL(matrix1[i][k]) * ULL(matrix2[k][j])) % MOD;
            result[i][j] %= MOD;
        }
    }

    return result;
}


template <typename type>
void MatrixPow(Matrix<type> &matrix, unsigned pow) {
    Matrix<type> result(matrix.size(), vector<type>(matrix.size(), 0));

    result[0][0] = 1;
    result[1][1] = 1;

    while (pow > 0) {
        if (pow & 1) {
            result = MatrixMultiply(result, matrix);
        }

        matrix = MatrixMultiply(matrix, matrix);
        pow >>= 1;
    }

    matrix = result;
}


void CloseFiles(ifstream &Read, ofstream &Write) {
    Read.close();
    Write.close();
}


int main() {
    unsigned k;
    Read >> k;

    if (k == 0) {
        Write << 0;
        CloseFiles(Read, Write);

        return 0;
    }

    Matrix<unsigned> matrix;

    InitMatrix(matrix);

    MatrixPow(matrix, k - 1);

    Write << matrix[1][1];

    CloseFiles(Read, Write);

    return 0;
}