#include <fstream>

#define mod 666013

using namespace std;

class Matrix {

    public:
        int V[2][2];

        void unit() {
            V[0][0] = V[1][1] = 1;
            V[0][1] = V[1][0] = 0;
        }

        void base() {
            V[0][0] = V[0][1] = V[1][0] = 1;
            V[1][1] = 0;
        }

        void operator *=(Matrix C) {

            int i, j, k;
            Matrix result;

            for(i = 0; i < 2; i++)
                for(j = 0; j < 2; j++) {
                    result.V[i][j] = 0;
                    for(k = 0; k < 2; k++)
                        result[i][j] = (result[i][j] + 1LL * V[i][k] * C[k][j]) % mod;
                }

            *this = result;
        }

        int * operator[](int index) {
            return V[index];
        }
};

int N;

int fibonacci(int power) {

    int mask;
    Matrix A, Answer;

    Answer.unit();
    A.base();

    for(mask = 1; mask <= power; mask <<= 1) {

        if(power & mask)
            Answer *= A;

        A *= A;
    }

    return Answer[0][1];

}
void Read() {

    ifstream in("kfib.in");
    in >> N;
    in.close();
}
void Write() {

    ofstream out("kfib.out");
    out << fibonacci(N) << '\n';
    out.close();
}
int main() {

    Read();
    Write();

    return 0;

}