#include<stdio.h>
#include<stdlib.h>
#include<fstream>
#include<iostream>


using namespace std;

const int mod=666013;
long long m[2][2]={{0,1},{1,1}};


long long aux_mm(long long a[][2], long long b[][2], int r, int c){
	long long rez=0*1LL;
	for(int i=0;i<=1;i++){
		rez=rez*1LL+a[r][i]*b[i][c]*1LL; 
	} 
	return rez%mod;
}

void matrix_multiplication(long long rez[][2], long long a[][2], long long b[][2]){	
	for(int r=0; r<2; r++)
	  for(int c=0; c<2; c++)
	     {rez[r][c]=aux_mm(a,b,r,c)*1LL;}
}


void copy(long long a[][2], long long b[][2]){
	for(int i=0;i<2;i++)
	  for(int j=0;j<2;j++)
	     a[i][j]=b[i][j]*1LL;
}


int main(){
	ifstream in; ofstream out;
	out.open("kfib.out"); in.open("kfib.in");
	out.clear();
	long long k,sol[2][2],rez[2][2];
	in>>k; 
	sol[0][0]=sol[1][1]=1; sol[0][1]=sol[1][0]=0;
	
	for(int i=0; (1<<i)<=k-1; i++){
		if(((1<<i)&(k-1))>0) {matrix_multiplication(rez,sol,m); copy(sol,rez);}
		matrix_multiplication(rez,m,m); copy(m,rez); 
	}
	
	
	if(k==0) out<<0;
	else if(k==1) out<<1;
	else  out<<sol[1][1];
	
	in.close(); out.close();
	return 0;
}