#include<fstream>
#define nr 666013
using namespace std;
long long n[3][3],rez[3][3];
void initn(){
	n[0][0]=0;
	n[0][1]=n[1][0]=n[1][1]=1;
}

void initrez(){
	rez[0][0]=rez[1][1]=1;
	rez[0][1]=rez[1][0]=0;
}
void inmrez(){
	int i,j,c[2][2],k;
	for(i=0;i<=1;i++)
		 for(j=0;j<=1;j++)
			 {
			  c[i][j]=0;
			  for(k=0;k<=1;k++)
			  {c[i][j]=(c[i][j]+n[i][k]*rez[k][j]%nr)%nr;
				}
     }
for(i=0;i<=1;i++)
		 for(j=0;j<=1;j++)
			 rez[i][j]=c[i][j];
}
void inmn(){
	int i,j,k;
	long long c[2][2];
	for(i=0;i<=1;i++)
		 for(j=0;j<=1;j++)
			 {
			  c[i][j]=0;
			  for(k=0;k<=1;k++)
			  {c[i][j]=(c[i][j]+n[i][k]*n[k][j]%nr)%nr;
				}
     }
for(i=0;i<=1;i++)
		 for(j=0;j<=1;j++)
			 n[i][j]=c[i][j];
}
int main(){
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	int k,i;
	f>>k;
	initn();
	initrez();
	for(i=0;(1<<i)<=k;i++)
{if(((1<<i)&k)!=0)inmrez();
inmn();
}
g<<rez[1][0];
}