#include <fstream>
#include <iostream>
#include <vector>

#define MOD 666013

using namespace std;
//Inmulteste matricele A si B. Rezultatul este returnat in matricea B.
//Operatiile sunt modulo MOD.

void afisare(vector< std::vector<int> >& A)
{
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			cout<<A[i][j]<<" ";
		}
		cout<<endl;
	}
}

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;
            }
        }
    }

    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] + A[i][j] * v[j]) % 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));
	    std::vector< std::vector<int> > aux(A.size(),std::vector<int>(A.size(), 0));
		;
    for (size_t i = 0; i < Res.size(); ++i) {
        Res[i][i] = 1;
    }

    //TODO
    //Caculati Res = pow(A, p)
	while(p!=0){
		
		if(p%2 != 0) 
			multiplyMatrix(A , Res);
		
		multiplyMatrix(A , A);
		
		p = p / 2 ;
	
	}
	
    A.swap(Res);
}

int main()
{
	int n;
	
	ifstream in("kfib.in");
	ofstream out("kfib.out");
	
	std::vector< std::vector<int> > A(2, std::vector<int>(2, 0));
    std::vector<int> count(2, 1);
	
	A[0][0] = A[0][1] = A[1][0] = 1;
	A[1][1] = 0;
	
	in>>n;
	
	logPowMatrix(A,n-1);
	multiplyMatrixVector(A, count);
	
	out<<count[1]<<endl;

}