#include <iostream>
#include <array>
#include <fstream>

class SquareMatrix {
private:
    std::array<long long, 4> matrix;
public:
    SquareMatrix(std::array<long long, 4> matrix) : matrix(matrix) {}
    SquareMatrix() {
        matrix = {1, 0, 0, 1};
    };

    int operator[](int index) {
        return matrix[index];
    }

    SquareMatrix operator*(const SquareMatrix& other) {
        SquareMatrix new_value;

        new_value.matrix[0] = this->matrix[0]*other.matrix[0] + this->matrix[1]*other.matrix[2];
        new_value.matrix[1] = this->matrix[0]*other.matrix[1] + this->matrix[1]*other.matrix[3];
        new_value.matrix[2] = this->matrix[2]*other.matrix[0] + this->matrix[3]*other.matrix[2];
        new_value.matrix[3] = this->matrix[2]*other.matrix[1] + this->matrix[3]*other.matrix[3];

        return new_value;
    }
};

SquareMatrix raise_power(SquareMatrix base, long long power) {

    SquareMatrix result;

    while(power) {
        if (power % 2 == 1)
            result = result * base;
        base = base * base;
        power /= 2;
    }

    return result;
}

int get_fibonacci(long long n) {
    if (n == 0) return 0;
    SquareMatrix fib_matrix = raise_power(SquareMatrix({0, 1, 1, 1}), n - 1);

    return fib_matrix[0] + fib_matrix[1];
}

int main()
{
    std::ifstream fin("kfib.in");
    std::ofstream fout("kfib.out");

    long long n;
    fin >> n;
    fout << get_fibonacci(n) % 666013;
}