#include <fstream>

using namespace std;

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

long long a[5][5],p[5][5],C[5][5];
int i,j,b,k;

void inmulteste ( long long p[5][5], long long a[5][5], long long C[5][5] ) {
	
	int i,j,k;
	for (i=1;i<=2;i++) 
		for (j=1;j<=2;j++) 
			C[i][j]=0;
	
	for (i=1;i<=2;i++) {
		for (j=1;j<=2;j++) 
			for (k=1;k<=2;k++) {
				C[i][j]+=((p[i][k])*(a[k][j]))%666013;
				C[i][j]%=666013;
			}
	}
}

void copiaza(long long a[5][5], long long b[5][5]){
	for (int i=1;i<=2;i++) 
		for (int j=1;j<=2;j++)
			b[i][j]=a[i][j];
}

int main () {
	
	
	for (i=1;i<=2;i++) 
		p[i][i]=1;
		
	fin>>k;
	a[1][1]=a[2][1]=a[1][2]=1;
	b=k-2;
	while (b!=0) {
		if (b%2==1) {
			inmulteste (p,a,C);
			copiaza (C,p);
		}
		inmulteste (a,a,C);
		copiaza (C,a);
		b/=2;
	}
	
	fout << (p[1][1]+p[1][2])%666013<<"\n";
	
	
	return 0;
}