#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD=666013;
int M[3][3],K;

void mult(int A[3][3],int B[3][3], int C[3][3]) {
	int i,j,k;
	for(i=1;i<3;i++)
		for(j=1;j<3;j++)
			for(k=1;k<3;k++)
				C[i][j]=(C[i][j] + (long long) A[i][k] * B[k][j]) % MOD;
}

void explog(int M[3][3], int P) {
	int A[3][3], AUX[3][3];
	
	A[1][1]=0; A[1][2]=1;
	A[2][1]=1; A[2][2]=1;
	
	while(P) {
		if(P&1) {
			memset(AUX,0,sizeof(AUX));
			mult(M,A,AUX);
			memcpy(M,AUX,sizeof(AUX));
		}
		
		memset(AUX,0,sizeof(AUX));
		mult(A,A,AUX);
		memcpy(A,AUX,sizeof(AUX));
		
		P/=2;
	}
}

int main() {
	fin >> K;
	
	M[1][1]=0; M[1][2]=1;
	
	explog(M,K-1);
	
	fout << M[1][2];
}