#include <fstream>

#define mod 666013

using namespace std;

class Matrix {

    private:
        int A[2][2];


    public:

        Matrix() {

            A[0][0] = A[0][1] = A[1][0] = A[1][1] = 0;

        }

        Matrix operator*(Matrix B) {

            int i, j, k;
            Matrix C;

            for(i = 0; i < 2; i++)
                for(j = 0; j < 2; j++)
                    for(k = 0; k < 2; k++)
                        C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;

            return C;

        }

        int * operator[](int index) {

            return A[index];

        }

};

int N, Result;

int Fib(int Power) {

    Matrix Base, result;

    Base[0][1] = Base[1][0] = Base[1][1] = 1;
    result[0][0] = result[1][1] = 1;

    for(int mask = 1; mask <= Power; mask <<= 1) {

        if(Power & mask)
            result = result * Base;

        Base = Base * Base;

        }

    return result[0][1];

}
void Read() {

    ifstream in("kfib.in");
    in >> N;
    in.close();

}
void Write() {

    ofstream out("kfib.out");
    out << Result << '\n';
    out.close();

}
int main() {

    Read();
    Result = Fib(N);
    Write();

    return 0;

}