#include <fstream>
using namespace std;

#define infile "kfib.in"
#define outfile "kfib.out"

#define MOD 666013

using namespace std;

class Matrix {
    public :

    int m[2][2];

    Matrix(){
        m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0;
    }

    Matrix(int a, int b, int c, int d){
        m[0][0] = a;
        m[0][1] = b;
        m[1][0] = c;
        m[1][1] = d;
    }

    Matrix :: Matrix operator * (Matrix &that){
        Matrix res = *new Matrix();

        for(int i=0; i<2; ++i)
            for(int j=0; j<2; ++j)
                for(int k=0; k<2; ++k)
                   res.m[i][j] = (1LL * res.m[i][j] + (1LL * m[i][k] * that.m[k][j])) % MOD;

        return res;
    }
};


Matrix powlog(Matrix N, int P){
    if(P == 1)
       return N;

    Matrix res = powlog(N,P/2);
    res = res * res;

    if(P&1)
      res = res * N;

    return res;
}


int main(){
    ifstream fin(infile);
    ofstream fout(outfile);

    int K;
    fin >> K;

    Matrix M = *new Matrix(1, 1, 1, 0);
    Matrix Fib = *new Matrix(1, 0, 0, 0);

    fout << (powlog(M, K) * Fib).m[1][0] <<'\n';

    fin.close();
    fout.close();

    return 0;
}