#include <bits/stdc++.h>
using namespace std;

#define MOD 666013
#define DIM 2

struct Matrix {
    int64_t mat[DIM][DIM];

    Matrix operator*(const Matrix& other) const {
        Matrix result = {{{0, 0}, {0, 0}}};

        for (int i = 0; i < DIM; ++i) {
            for (int j = 0; j < DIM; ++j) {
                for (int k = 0; k < DIM; ++k) {
                    result.mat[i][j] = (result.mat[i][j] + (mat[i][k] % MOD)
                                      * (other.mat[k][j] % MOD) % MOD) % MOD;
                }
            }
        }
        return result;
    }
};

class Task { // O(log n)
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    int64_t k;

    void read_input() {
        ifstream fin("kfib.in");
        fin.tie(0);
        
        fin >> k;

        fin.close();
    }

    Matrix matrix_pow(Matrix base, int64_t exp) {
        Matrix result = {{{1, 0}, {0, 1}}};

        while (exp > 0) {
            if (exp % 2 == 1) {
                result = result * base;
            }
            base = base * base;
            exp /= 2;
        }

        return result;
    }

    int64_t get_result() {
        Matrix C = {{{0, 1}, {1, 1}}};

        Matrix C_k = matrix_pow(C, k - 2);

        return (C_k.mat[0][1] + C_k.mat[1][1]) % MOD;
    }

    void print_output(int result) {
        ofstream fout("kfib.out");
        
        fout << result << "\n";

        fout.close();
    }
};

int main() {
    ios::sync_with_stdio(false);
    auto* task = new (nothrow) Task();

    if (!task) {
        cerr << "new failed\n";
        return -1;
    }

    task->solve();
    delete task;

    return 0;
}