#include <bits/stdc++.h>

// what the fuck
template<typename T, int N>
struct NDVector { using type = std::vector<typename NDVector<T, N - 1>::type>; };
template<typename T>
struct NDVector<T, 1> { using type = std::vector<T>; };

// A tensor is essentially a vector of tensors. (or multidimensional array)
template<typename T, int N>
using Tensor = typename NDVector<T, N>::type;

/**
 * Create a multidimensional vector with the given dimension sizes.
 *
 * In particular, create_vector(N) = create_tensor(N), create_matrix(N, M) = create_tensor(N, M).
 * If you have some weird multidimensional DP, you can create the DP table by doing:
 *      dp = create_tensor(5, 5, 5, 5, 5);
 *
 * Be careful, for a large number of dimensions, this uses a lot of memory and is very cache unfriendly.
 */
template<typename T>
std::vector<T> create_tensor(int N) {
    return std::vector<T>(N);
}
template <typename T, typename... ArgTypes>
Tensor<T, sizeof...(ArgTypes) + 1> create_tensor(int N, ArgTypes... args) {
    auto under = create_tensor<T>(args...);
    return std::vector(N, under);
}

/**
 * Create a matrix of the given dimensions.
 */
template<typename T>
Tensor<T, 2> create_matrix(int N, int M) {
    return create_tensor<T>(N, M);
}

/**
 * Frequently used definitions, like Vector, Matrices, pairs of ints, pairs, triples, etc.
 */
template<typename T>
using Vector = Tensor<T, 1>; // I could use std::vector<T>, but this is just too cool.
template<typename T>
using Matrix = Tensor<T, 2>;

template<typename T1, typename T2>
using Pair = std::pair<T1, T2>;
using PairII = Pair<int, int>;
using PairLL = Pair<long long, long long>;

template<typename T1, typename T2, typename T3>
using Triple = std::tuple<T1, T2, T3>;

/**
 * Read a vector from input. Set start to 1 if you want it to be 1-indexed.
 */
template<typename T>
Vector<T> read_vector(int N, int start = 0) {
    Vector<T> v(start + N);
    for (int i = start; i < (int)v.size(); i++) {
        std::cin >> v[i];
    }
    return v;
}

/**
 * Read a matrix from input. Set start_l to make lines 1-indexed. Same thing for start_c.
 */
template<typename T>
Matrix<T> read_matrix(int N, int M, int start_l = 0, int start_c = 0) {
    Matrix<T> matr = create_matrix<T>(N + start_l, M + start_c);

    for (int l = start_l; l < N + start_l; l++)
        for (int c = start_c; c < M + start_c; c++)
            std::cin >> matr[l][c];

    return matr;
}

/**
 * Print a tensor to the output stream. Prints all indices between i and j, and the elements 
 * are separated by the given separator.
 *
 * To generalize, for each dimension, you give the bounds that you want to print and the separator
 * between each order. To print a matrix, you would do:
 *
 *      print_tensor(matr, std::cout, 0, N - 1, "\n", 0, M - 1, " ");
 */
template<typename T>
void print_tensor(Tensor<T, 1>& tens, std::ostream&fout, int i, int j, const char* sep) {
    for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
        fout << tens[t];
        if (t + 1 <= j)
            fout << sep;
    }
}

template<typename T, typename... Sizes>
void print_tensor(
        Tensor<T, sizeof...(Sizes) / 3 + 1>& tens,
        std::ostream& fout, 
        int i, int j, const char* sep, Sizes... sizes) {
    for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
        print_tensor<T>(tens[t], fout, sizes...);
        if (t + 1 <= j)
            fout << sep;
    }
}

/**
 * Print a vector to the given output stream with given bounds and separator.
 */
template<typename T>
void print_vector(std::vector<T>& v, std::ostream& fout, int i = 0, int j = (1 << 30), const char* sep = " ") {
    print_tensor<T>(v, fout, i, j, sep);
}

/**
 * Read a vector of pairs. Set start to 1 if you want this to be 1-indexed.
 */
template<typename T1, typename T2>
Vector<Pair<T1, T2>> read_pairvec(int N, int start = 0) {
    Vector<Pair<T1, T2>> input = Vector<Pair<T1, T2>>(start + N);
    for (int i = start; i < start + N; i++)
        std::cin >> input[i].first >> input[i].second;
    return input;
}

/**
 * Read a vector of triples. Set start to 1 if you want this to be 1-indexed.
 *
 * If you need higher order tuples, like quadruples, you're better off using a matrix instead.
 */
template<typename T1, typename T2, typename T3>
Vector<Triple<T1, T2, T3>> read_triplevec(int N, int start = 0) {
    Vector<Triple<T1, T2, T3>> input = Vector<Triple<T1, T2, T3>>(start + N);
    for (int i = start; i < N + start; i++) {
        T1 a;
        T2 b;
        T3 c;
        std::cin >> a >> b >> c;
        input[i] = {a, b, c};
    }
    return input;
}

/**
 * Removes duplicates from vector. Assumes it is sorted.
 */
template<typename T>
void deduplicate(Vector<T>& v) {
    v.resize(std::unique(v.begin(), v.end()) - v.begin());    
}

/**
 * Solve a testcase of the problem. You will code your solution here instead of main.
 */
void solve_test();

/**
 * Call this function if you have a problem with multiple testcases.
 */
void multitest_problem() {
    int T;
    std::cin >> T;

    while (T--) solve_test();
}

int main() {
    std::cin.tie(NULL);
    std::iostream::sync_with_stdio(false);

    // Choose one of the following functions, depending on the problem type.
    solve_test();
    //multitest_problem();

    return 0;
}

/******************************************** modulo.h ******************************************/

/**
 * Classic modulos. The third one is not const in case you need dynamic modulo operations.
 */
const int MOD = 666013;
//const int MOD = 1000000007;
//int MOD = 1234;

/**
 * Modulo class that encapsulates all the modulo operations. Addition, multiplication, subtraction.
 */
struct Modulo {
    int val;
    
    Modulo(long long v = 0) { v %= MOD; if (v < 0) v += MOD; val = v; }
    
    Modulo& operator+=(Modulo const& x) { 
        val = val + x.val;
        if (val >= MOD)
            val = val - MOD;
        return *this;
    }
    Modulo& operator-=(Modulo const& x) { 
        val = val - x.val;
        if (val < 0)
            val = val + MOD;
        return *this;
    }
    Modulo& operator*=(Modulo const& x) { 
        val = (long long)val * x.val % MOD;
        return *this;
    }

    friend Modulo operator+(Modulo a, Modulo const b) { return a += b; }
    friend Modulo operator-(Modulo a, Modulo const b) { return a -= b; }
    friend Modulo operator-(Modulo const b) { return 0 - b; }
    friend Modulo operator*(Modulo a, Modulo const b) { return a *= b; }
    friend std::ostream& operator<<(std::ostream& fout, Modulo const x) { return fout << x.val; }

    friend bool operator==(Modulo const a, Modulo const b) { return a.val == b.val; }
    friend bool operator!=(Modulo const a, Modulo const b) { return a.val != b.val; }
};

/**
 * Binary exponentiation of modulo numbers.
 */
Modulo lgput(Modulo b, long long e) {
    Modulo ac = 1;
    while (e > 0) {
        if (e % 2 == 1)
            ac = ac * b;
        b = b * b;
        e /= 2;
    }
    return ac;
}

/**
 * Compute the inverse of the given modulo number.
 * 
 * XXX: MOD must be a prime number. Otherwise you have to do some crazy stuff.
 */
Modulo inverse(Modulo a) {
    return lgput(a, MOD - 2);
}

/************************************* linear-algebra.h *********************************/ 

template<typename T>
struct LinVector {
    std::vector<T> val;

    explicit LinVector(int N, std::vector<T> data = {}): val(N) {
        for (int i = 0; i < N; i++)
            if (i < (int)data.size())
                val[i] = data[i];
    }

    explicit LinVector(int N, int i): val(N) {
        val[i] = 1; 
    }

    LinVector<T>& operator+=(LinVector<T>& other) {
        assert(val.size() == other.val.size());
        for (int i = 0; i < (int)val.size(); i++)
            val[i] += other.val[i];
        return *this;
    }
    LinVector<T>& operator-=(LinVector<T>& other) {
        assert(val.size() == other.val.size());
        for (int i = 0; i < val.size(); i++)
            val[i] -= other.val[i];
        return *this;
    }
    LinVector<T>& operator*(T other) {
        for (int i = 0; i < val.size(); i++)
            val[i] *= other;
        return *this;
    }
    T& operator[](int pos) {
        assert(0 <= pos && pos < (int)val.size());
        return val[pos];
    }
    friend LinVector<T> operator+(LinVector<T> a, LinVector<T> b) { return a += b; }
    friend LinVector<T> operator-(LinVector<T> a, LinVector<T> b) { return a -= b; }
    friend T operator*(LinVector<T> a, LinVector<T> b) { 
        T res = 0;
        for (int i = 0; i < (int)a.val.size(); i++)
            res = res + a[i] * b[i];
        return res; 
    }
    friend LinVector<T> operator*(LinVector<T> a, T b) { return a *= b; }
    int size() const { return val.size(); }
};

/**
 * Matrix data structure used for linear algebra.
 */
template<typename T>
struct LinMatrix {
    std::vector<LinVector<T>> val;

    /**
     * Complete matrix elements line by line, from left to right, as long as there is enough place. Good for manual testing
     * 
     * For instance:
     *      LinMatrix<int> x(3);
     *      x = {1, 2, 3, 4, 5, 6, 7}; // first two rows look as you would expect
     *                                 // last row is {7, 0, 0};
     */
    LinMatrix<T>& operator= (std::vector<T> v) {
        auto [N, M] = size();
        int p = 0;
        for (int l = 0; l < N; l++)
            for (int c = 0; c < M; c++) {
                if (p < (int)v.size())
                    val[l][c] = v[p++];
                else
                    val[l][c] = 0;
            }
        return *this;
    }

    LinMatrix(int N, int M, std::vector<T> x = {}): val(N, LinVector<T>(M)) {
        *this = x;
    }
    LinMatrix(int N, std::vector<T> x = {}): LinMatrix(N, N, x) {}
    LinMatrix(): LinMatrix(0, 0) {}

    /**
     * Return sizes of the matrix.
     */
    std::pair<int, int> size() const {
        int N = val.size();
        if (N == 0) return {0, 0};
        return {N, val[0].size()};
    }

    /**
     * Returns the given **row** of the matrix.
     */
    LinVector<T>& operator[](int pos) {
        return val[pos];
    }

    /**
     * Returns the given column of the matrix.
     */
    LinVector<T> column(int pos) {
        auto [N, M] = size();
        LinVector<T> res(N);
        for (int i = 0; i < N; i++)
            res[i] = val[i][pos];
        return res;
    }

    /**
     * Returns the transpose of the matrix.
     */
    LinMatrix<T> transpose() {
        auto [N, M] = size();
        LinMatrix<T> res(M, N);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                res[j][i] = val[i][j];
        return res;
    }

    /**
     * Standard matrix operations. Addition, subtraction, multiplication.
     *
     * If you need another underlying data structure, you do not have to implement all operations.
     */
    LinMatrix<T>& operator+= (const LinMatrix<T>& b) {
        assert(size() == b.size());
        auto [n, m] = size();
        for (int i = 0; i < n; i++)
            val[i] = val[i] + b[i];
        return *this;
    }

    LinMatrix<T>& operator-= (const LinMatrix<T>& b) {
        assert(size() == b.size());
        auto [n, m] = size();
        for (int i = 0; i < n; i++)
            val[i] = val[i] - b[i];
        return *this;
    }

    friend LinMatrix<T> operator+ (LinMatrix<T> a, const LinMatrix<T>& b) {
        return a += b;
    }

    friend LinMatrix<T> operator* (LinMatrix<T>& a, LinMatrix<T>& b) {
        auto [N, M] = a.size();
        auto [M2, K] = b.size();

        assert(M == M2);

        LinMatrix res(N, K);

        auto bt = b.transpose();

        for (int l = 0; l < N; l++)
            for (int c = 0; c < K; c++)
                res[l][c] = a[l] * bt[c];
        return res;
    }

    friend LinVector<T> operator* (LinMatrix<T> a, LinVector<T> b) {
        auto [N, M] = a.size();
        auto N2 = b.size();

        assert(M == N2);

        LinVector<T> res(N);
        for (int i = 0; i < N; i++)
            res[i] = a[i] * b;

        return res;
    }

    LinMatrix<T>& operator *= (const LinMatrix& a) {
        auto res = (*this) * a;
        val = std::move(res.val);
        return *this;
    }


    friend std::ostream& operator<<(std::ostream& fout, LinMatrix<T>& v) {
        auto [N, M] = v.size();

        for (int l = 0; l < N; l++) {
            for (int c = 0; c < N; c++)
                fout << v.val[l][c] << " ";
            fout << "\n";
        }
        return fout;
    }
};

/**
 * Create the identity matrix of size N.
 */
template<typename T>
LinMatrix<T> identitymatrix(int N, T e = 1, T n = 0) {
    LinMatrix<T> res(N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (i == j)
                res.val[i][j] = e;
            else
                res.val[i][j] = n;
    return res;
}

/**
 * Create the null matrix of size N.
 */
template<typename T>
LinMatrix<T> nullmatrix(int N, T n = 0) {
    LinMatrix<T> res(N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            res.val[i][j] = n;
    return res;
}

/**
 * Logarithmic exponentiation.
 */
template<typename T>
LinMatrix<T> lgput(LinMatrix<T> A, int e, T neutral = 1, T null = 0) {
    auto [N, M] = A.size();
    assert(N == M);

    LinMatrix<T> ac = identitymatrix(N, neutral, null);

    while (e > 0) {
        if (e % 2 == 1)
            ac = ac * A;
        A = A * A;
        e /= 2;
    }
    
    return ac;
}

/**
 * Some Voodoo structs used to create a linear recurrence matrix while you also code
 * just the bruteforce solution.
 */
template<typename T>
struct LinearRecurrenceBuidler;
template<typename T>
struct LinearRecurrenceReference;
template<typename T>
struct LinearRecurrenceBuilder {
    LinMatrix<T> mat;
    LinVector<T> init;
    int N;
    int last_id = 1; // 0 is reserved for constants.

    /**
     * Create a linear recurrence with N variables. The first value is reserved
     * for constants.
     */
    LinearRecurrenceBuilder(int N): mat(1 + N), init(1 + N), N(1 + N) {
        init[0] = 1;
        for (int i = 0; i < N; i++)
            mat[i][i] = 1;
    }

    /**
     * Create a new variable used in the linear recurrence.
     */
    LinearRecurrenceReference<T> create_variable(T val) {
        assert(last_id < N);
        int id = last_id;
        last_id++;

        LinearRecurrenceReference<T> res(*this, id, true, LinVector<T>(N, id));
        res.init_flag = true;
        init[id] = val;

        return res;
    }

    /**
     * Run the recurrence for K steps, where K can be arbitrarily large.
     *
     * After running this function, you should not modify the variables anymore, you 
     * should just read their values.
     */
    void run_recurrence(int64_t K) {
        init = lgput(mat, K) * init;
    }
};

/**
 * Reference to a variable. You should be able to use all these variables
 * as you would in a normal DP, without using the matrix exponentiation, but
 * the cool thing is that under the hood, all the operations that you do are 
 * recorded so that in the end you can build the recurrence matrix.
 *
 * All operators run in O(N) where N is the number of used variables.
 */
template<typename T>
struct LinearRecurrenceReference {
    LinearRecurrenceBuilder<T>& builder;
    int index;
    bool base;
    LinVector<T> coef;
    bool init_flag = false; // The builder must set this to true.

    LinearRecurrenceReference(
        LinearRecurrenceBuilder<T>& builder,
        int index, bool base, LinVector<T> _coef) :
        builder(builder), index(index), base(base), coef(_coef) {}

    LinearRecurrenceReference(
        LinearRecurrenceReference<T>& other
    ) : builder(other.builder), coef(other.coef) {
        index = other.index;
        if (other.init_flag)
            base = other.base;
        else
            base = false;
        coef = other.coef;
    }

    LinearRecurrenceReference<T>& operator= (LinearRecurrenceReference<T>& other) {
        coef = other.coef;
        if (base)
            builder.mat[index] = coef;
        return *this;
    }
    LinearRecurrenceReference<T>& operator= (T other) {
        int N = coef.size();
        coef = LinVector<T>(N);
        coef[0] = other;
        if (base)
            builder.mat[index] = coef;
        return *this;
    }

    friend LinearRecurrenceReference<T> operator+ (
            LinearRecurrenceReference<T>& a,
            LinearRecurrenceReference<T>& b
    ) {
        return LinearRecurrenceReference<T>(a.builder, -1, false, a.coef + b.coef);
    }
    friend LinearRecurrenceReference<T> operator+ (
            LinearRecurrenceReference<T>& a,
            int b
    ) {
        LinVector<T> ct(a.coef.size());
        ct[0] = b;
        return LinearRecurrenceReference<T>(a.builder, -1, false, a.coef) +
                LinearRecurrenceReference<T>(a.builder, -1, false, ct);
    }
    friend LinearRecurrenceReference<T> operator- (
            LinearRecurrenceReference<T>& a,
            LinearRecurrenceReference<T>& b
    ) {
        return LinearRecurrenceReference<T>(a.builder, -1, false, a.coef - b.coef);
    }
    friend LinearRecurrenceReference<T> operator- (
            LinearRecurrenceReference<T>& a,
            int b
    ) {
        LinVector<T> ct(a.coef.size());
        ct[0] = b;
        return LinearRecurrenceReference<T>(a.builder, -1, false, a.coef) - 
                LinearRecurrenceReference<T>(a.builder, -1, false, ct);
    }
    friend LinearRecurrenceReference<T> operator* (
            LinearRecurrenceReference<T>& a,
            int b
    ) {
        return LinearRecurrenceReference<T>(a.builder, -1, false, a.coef * b);
    }
    friend LinearRecurrenceReference<T> operator* (
            int b,
            LinearRecurrenceReference<T>& a
    ) {
        return LinearRecurrenceReference<T>(a.builder, -1, false, a.coef * b);
    }

    LinearRecurrenceReference<T>& operator+=(
            LinearRecurrenceReference<T>& b
    ) { return (*this = *this + b); }
    LinearRecurrenceReference<T>& operator+=(
            int b
    ) { return (*this = *this + b); }
    LinearRecurrenceReference<T>& operator-=(
            LinearRecurrenceReference<T>& b
    ) { return (*this = *this - b); }
    LinearRecurrenceReference<T>& operator-=(
            int b
    ) { return (*this = *this + b); }
    LinearRecurrenceReference<T>& operator*=(
            T b
    ) { return (*this = *this * b); }

    /**
     * Does not work if you ran the recurrence.
     */
    T current_value() {
        return builder.init * coef;
    }

    /**
     * Get current value of the variable, use this after you ran the recurrence.
     */
    T value() {
        return builder.init[index];
    }
};

void solve_test() {
    std::ifstream fin("kfib.in");
    std::ofstream fout("kfib.out");

    int K;
    fin >> K;

    LinearRecurrenceBuilder<Modulo> builder(2);

    auto f0 = builder.create_variable(0);
    auto f1 = builder.create_variable(1);

    // for (int i = 1; i <= K; i++) {
    {
        auto fs = f0 + f1;
        f0 = f1;
        f1 = fs;
    }

    builder.run_recurrence(K);
    fout << f0.value();
}