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

#define MOD 666013

using namespace std;

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

vector<vector<uint64_t>> multiplyMatrix(vector<vector<uint64_t>> matrixA, vector<vector<uint64_t>> matrixB)
{
    int r1 = matrixA.size();
    int c1 = matrixA[0].size();
    int r2 = matrixB.size();
    int c2 = matrixB[0].size();


    vector<vector<uint64_t>> newMatrix(r1, vector<uint64_t>(c2, 0));

    if (c1 != r2)
    {
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < r1; i++)
    {
        for (int j = 0; j < c2; j++)
        {
            for (int k = 0; k < c1; k++)
            {
                newMatrix[i][j] = newMatrix[i][j] + matrixA[i][k] * matrixB[k][j];
                newMatrix[i][j] = newMatrix[i][j] % MOD;
            }
        }
    }

    return newMatrix;
}

void printMatrix(vector<vector<uint64_t>> matrix)
{
    for (long unsigned int i = 0; i < matrix.size(); i++, cout << '\n')
    {
        for (long unsigned int j = 0; j < matrix[0].size(); j++)
        {
            cout << matrix[i][j] << ' ';
        }
    }
}

vector<vector<uint64_t>> powMatrix(vector<vector<uint64_t>> matrix, uint64_t p)
{
    vector<vector<uint64_t>> resultMatrix(2, vector<uint64_t>(2, 0));

    if (p == 0)
    {
        resultMatrix[0][0] = resultMatrix[1][1] = 1;

        return matrix;
    }

    if (p == 1)
    {
        return matrix;
    }

    if ((p & 1) == 1)
    {
        p--;
        resultMatrix = powMatrix(matrix, p / 2);
        resultMatrix = multiplyMatrix(resultMatrix, resultMatrix);
        resultMatrix = multiplyMatrix(resultMatrix, matrix);

        return resultMatrix;
    }

    resultMatrix = powMatrix(matrix, p / 2);
    resultMatrix = multiplyMatrix(resultMatrix, resultMatrix);

    return resultMatrix;
}

int main()
{
    uint64_t k = 0;

    fin >> k;
    vector<vector<uint64_t>> fiboMatrix = {{0, 1}, {1, 1}};

    fiboMatrix = powMatrix(fiboMatrix, k);

    uint64_t result = fiboMatrix[0][1];

    fout << result << '\n';

    return 0;
}