#include <iostream>
#include <fstream>
#include <vector>
 
#define MOD 666013
 
using namespace std;
 
 
//Inmulteste matricele A si B. Rezultatul este returnat in matricea B.
//Operatiile sunt modulo MOD.
inline void multiplyMatrix(
    std::vector< std::vector<int> >& A,
    std::vector< std::vector<int> >& B
) {
    const size_t N = A.size();
    const size_t M = B[0].size();
    const size_t K = A[0].size();
 
    std::vector< std::vector<int> > Res(N, std::vector<int>(M, 0));
 
    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < M; ++j) {
            for (size_t k = 0; k < K; ++k) {
                Res[i][j] = (Res[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
            }
			//if (Res[i][j] < 0) Res[i][j] += MOD;
        }
    }
 
    B.swap(Res);
}
 
//Inmulteste matricea A cu vectorul v. Rezultatul este returnat in vectorul v.
//Operatiile sunt modulo MOD
inline void multiplyMatrixVector(
    std::vector< std::vector<int> >& A,
    std::vector<int>& v
) {
    const size_t N = A.size();
    const size_t M = v.size();
 
    std::vector<int> vRes(N, 0);
 
    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < M; ++j) {
            vRes[i] = (vRes[i] + v[j] * A[j][i]) % MOD;
        }
    }
 
    v.swap(vRes);
}

//Ridica la puterea p matricea patratica A. Matricea finala este returnata in A.
//Operatiile sunt modulo MOD.
inline void logPowMatrix(std::vector< std::vector<int> >& A, int p) {
    std::vector< std::vector<int> > Res(A.size(),std::vector<int>(A.size(), 0));
 
    for (size_t i = 0; i < Res.size(); ++i) {
        Res[i][i] = 1;
    }
 
    for (int i = 0; (1 << i) <= p; ++i) {
        if (((1 << i) & p) > 0) {
            multiplyMatrix(A, Res);
        }
        multiplyMatrix(A, A);
    }
 
    A.swap(Res);
}
 
 
ifstream  fin("kfib.in");
ofstream fout("kfib.out");
 
int N, K, n, k;
vector<vector<int> > M(2, vector<int>(2, 0));
 
int main() {
    fin >> N;

	M[0][1] = M[1][0] = M[1][1] = 1;

	logPowMatrix(M, N);

	fout << M[1][0] % MOD << '\n';

    return 0;
}