/**
 * https://www.youtube.com/watch?v=eMXNWcbw75E&t=1694s&ab_channel=Errichto
 * min 25. + pe classroom))))
 *
 * a = 0;
 * b = 1;
 *
 * for(int i = 2;i <= n;++i) {
 *      int new_a = a * 0 + 1 * b;
 *      int new_b = 1 * a + 1 * b;
 *
 *      a = new_a
 *      b = new_b
 * }
 *
 * rezulta matricea A
 *
 * A = (0, 1)
 *     (1, 1)
 *  A^N = al n lea termen fibonacci
 * */

#include <fstream>
#include <vector>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;

struct Matrix {

private:

    int rows;
    int cols;
    vector < vector < unsigned long long > > content;

    Matrix power(Matrix a, unsigned long long b) {

        Matrix ret(a.rows, a.cols);

        for(int i = 0;i < a.rows;++i)
            ret.at(i, i) = 1;

        for(;b;) {

            if(b % 2 == 1)
                ret = ret * a;

            a = a * a;
            b /= 2;
        }

        return ret;
    }

public:

    Matrix(int rows, int cols): rows(rows), cols(cols) {
        content.resize(rows, vector < unsigned long long >(cols, 0));
    }

    unsigned long long& at(int row, int col) {
        return content[row][col];
    }

    Matrix operator*(Matrix& rhs) {

        Matrix ret(rows,rhs.cols);

        for(int i = 0;i < rows;++i)
            for(int j = 0;j < cols;++j)
                for(int k = 0;k < cols;++k)
                    ret.at(i, j) = (ret.at(i, j) + this->at(i, k) * rhs.at(k, j)) % MOD;

        return ret;
    }

    Matrix operator^(unsigned long long n) {
        return power(*this, n);
    }
};

Matrix createMatrix() {

    Matrix ret(2, 2);

    for(int i = 0;i < 2;++i)
        for(int j = 0;j < 2;++j)
            ret.at(i, j) = 1;

    ret.at(0, 0) = 0;

    return ret;
}

int main() {

    unsigned long long n;
    f >> n;

    if (n == 0) {
        g << 0;
    } else {

        n++;
        Matrix res = createMatrix();
        g << (res ^ n).at(0, 0);
    }

    return 0;
}