#include<stdio.h>
#define MOD 666013
using namespace std;
long long int A[3][3],B[3][3];
FILE *f=fopen("kfib.in","r");
FILE *g=fopen("kfib.out","w");
long int k;
void inmultire(long long int A[3][3],long long  int B[3][3]){
	long long int aux=0,C[3][3];
	for(int i=1;i<=1;i++){
		for(int j=1;j<=2;j++){
			aux=0;
			for(int kk=1;kk<=2;kk++)
				aux +=(A[i][kk]*B[kk][j]%MOD)%MOD;
			C[i][j]=aux%MOD;
		}
	}
	for(int i=1;i<=2;i++)
		A[1][i]=C[1][i];
}
void inmultire2(long long int X[3][3],long long int B[3][3]){
	long long int aux=0,C[3][3];
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			aux=0;
			for(int kk=1;kk<=2;kk++)
				aux+=(((X[i][kk])*(B[kk][j]))%MOD)%MOD;
			C[i][j]=aux%MOD;
		}
	}
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			X[i][j]=C[i][j];
}
int main (){
	fscanf(f,"%d",&k);
	A[1][1]=0,A[1][2]=1;
	B[1][1]=0,B[1][2]=1,B[2][1]=1,B[2][2]=1;
	
	for(k--;k>0;k/=2){
		if(k%2!=0)
			inmultire(A,B);
		inmultire2(B,B);
	}
	
	fprintf(g,"%d ",A[1][2]);
	return 0;
}