#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define mod 666013

void inm(long long int a[][2],long long int b[][2],long long int c[][2]) {
	int i, j;
	for (i = 0; i < 2; i++)
		for (j = 0; j < 2; j++)
				c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % mod;
}

void copiere(long long int a[][2],long long int b[][2]){
	a[0][0]=b[0][0];
	a[0][1]=b[0][1];
	a[1][0]=b[1][0];
	a[1][1]=b[1][1];
}

void power(long long int n,long long int sol[][2],long long int Z[][2]){
	long long int aux[2][2];
	while(n>0){
		if(n&1){
			inm(sol,Z,aux);
			copiere(sol,aux);
		}
		n=n>>1;
		inm(Z,Z,aux);
		copiere(Z,aux);
	}
}


int main(){
	long long int n,sol[2][2],Z[2][2];
	FILE *f,*g;
	if((f=fopen("kfib.in","r"))==NULL){
		printf("eroare fisier\n");
		exit(1);
	}
	if((g=fopen("kfib.out","w"))==NULL){
		printf("eroare fisier\n");
		exit(1);
	}
	fscanf(f,"%lld",&n);
	
	Z[0][0]=0; Z[0][1]=1; Z[1][0]=1; Z[1][1]=1;
	sol[0][0]=1; sol[0][1]=0; sol[1][0]=0; sol[1][1]=1;
	power(n-1,sol,Z);
	
	fprintf(g,"%lld\n",sol[1][1]);
			
	fclose(f);
	fclose(g);
	return 0;
}