#include<fstream>
#define Nmax 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int  n,a[2][2],m[2][2];
void inm(int a[][2],int m[][2]){   
	int i,j,k;    
	int aux[2][2]={{0,0},{0,0}};    
	for(i=0;i<=1;++i)    
		for(j=0;j<=1;++j)    
			for(k=0;k<=1;++k)   
				aux[i][j]=(aux[i][j]+1ll*a[i][k]*m[k][j])%Nmax;    
			for(i=0;i<=1;++i)   
				for(j=0;j<=1;++j)    
					a[i][j]=aux[i][j];
}
void putere(int a[][2],int p){    
	while(p){
		if(p&1)
			inm(a,m);
		p/=2;    
		inm(m,m);    
	}
}
int main(){    
f>>n;    
m[0][1]=m[1][0]=m[1][1]=1;    
a[0][0]=a[1][1]=1;   
putere(a,n-1);    
g<<a[1][1]<<'\n';    
return 0;
}