#include<fstream>
using namespace std;
#define MOD 666013
int C[2][2][100000],D[100000],Answer[100000];
long long K;
int AW[1000],BY[100000],AX[100000],BZ[100000],CW[100000],DY[100000],CX[100000],DZ[100000];
int CC[2][2][2];

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

int mod(int A[], int B){
      int i, t = 0;
      for (i = A[0]; i > 0; i--)
              t = (t * 10 + A[i]) % B;
      return t;
}

void suma(int A[],int B[],int C[]){
	int i,size= A[0]>B[0]? A[0]:B[0],t;
	for(i=1;i<=size || t;i++,t/=10)
		C[i]= (t+= A[i]+B[i]) % 10;
	C[0]=i-1;
}

void produs(int A[], int B[],int C[]){
      int i, j, t;
      memset(C, 0, 1000*sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
}

void descompune(long long k){
	while(k!=1){
			D[++D[0]]=k%2;
			if(k%2)
				k--;
			else
				k/=2;
	}
}

void reverse(int D[]){
	int aux;
	for(int i=D[0],j=1;j<i;i--,j++)
		aux=D[i],D[i]=D[j],D[j]=aux;;
}

void rezolva(){
	for(int i=1;i<=D[0];i++){
		if(D[i]==0){
			produs(C[0][0],C[0][0],AW);
			produs(C[0][1],C[1][0],BY);
			produs(C[0][0],C[0][1],AX);
			produs(C[0][1],C[1][1],BZ);
			produs(C[1][0],C[0][0],CW);
			produs(C[1][1],C[1][0],DY);
			produs(C[1][0],C[0][1],CX);
			produs(C[1][1],C[1][1],DZ);
			suma(AW,BY,C[0][0]);
			suma(AX,BZ,C[0][1]);
			suma(CW,DY,C[1][0]);
			suma(CX,DZ,C[1][1]);
		}
		if(D[i]==1){
			produs(C[0][0],CC[0][0],AW);
			produs(C[0][1],CC[1][0],BY);
			produs(C[0][0],CC[0][1],AX);
			produs(C[0][1],CC[1][1],BZ);
			produs(C[1][0],CC[0][0],CW);
			produs(C[1][1],CC[1][0],DY);
			produs(C[1][0],CC[0][1],CX);
			produs(C[1][1],CC[1][1],DZ);
			suma(AW,BY,C[0][0]);
			suma(AX,BZ,C[0][1]);
			suma(CW,DY,C[1][0]);
			suma(CX,DZ,C[1][1]);
		}
	}
	
	
}

void afiseaza(){
	suma(C[0][0],C[1][0],Answer);
	fout<<mod(Answer,MOD)<<"\n";
}

int main(){
	
	C[0][0][0]=1;
	C[0][0][1]=0;
	C[0][1][0]=1;
	C[0][1][1]=1;
	C[1][0][0]=1;
	C[1][0][1]=1;
	C[1][1][0]=1;
	C[1][1][1]=1;
	
	CC[0][0][0]=1;
	CC[0][0][1]=0;
	CC[0][1][0]=1;
	CC[0][1][1]=1;
	CC[1][0][0]=1;
	CC[1][0][1]=1;
	CC[1][1][0]=1;
	CC[1][1][1]=1;
	
	fin>>K;
	
	descompune(K-1);
	reverse(D);
	
	rezolva();
	
	afiseaza();
	
	fin.close();
	fout.close();
	return 0;
}