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

class SquareMatrix {
private:
    std::array<unsigned long long, 4> matrix;
public:
    SquareMatrix(std::array<unsigned 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] = (1LL * this->matrix[0]*other.matrix[0] + 1LL * this->matrix[1]*other.matrix[2]) % 666013;
        new_value.matrix[1] = (1LL * this->matrix[0]*other.matrix[1] + 1LL * this->matrix[1]*other.matrix[3]) % 666013;
        new_value.matrix[2] = (1LL * this->matrix[2]*other.matrix[0] + 1LL * this->matrix[3]*other.matrix[2]) % 666013;
        new_value.matrix[3] = (1LL * this->matrix[2]*other.matrix[1] + 1LL * this->matrix[3]*other.matrix[3]) % 666013;

        return new_value;
    }
};

SquareMatrix raise_power(SquareMatrix base, unsigned long long power) {

    SquareMatrix result;

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

    return result;
}

int get_fibonacci(unsigned 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]) % 660634;
}

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

    long long n;
    fin >> n;
    long long fib = get_fibonacci(n);
    fout << fib;
}