#include<fstream>
using namespace std;
int z[2][2],sol[2][2],tmp[2][2],n;
inline void inmultire(int a[][2],int b[][2]) {
	int i,j,k;
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			for(k=0;k<2;k++)
				tmp[i][j]=(tmp[i][j]+1LL*a[i][k]*b[k][j])%666013;
}
inline void mat_pow(int p) {
	int i,j;
	while(p)
		{if(p%2==0)
			{inmultire(z,z);p/=2;
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
					z[i][j]=tmp[i][j],tmp[i][j]=0;
			}
		else
			{inmultire(sol,z),p--;
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
					sol[i][j]=tmp[i][j],tmp[i][j]=0;
			}
		}
}
int main() {
	ifstream in("kfib.in");
	in>>n;
	in.close();
	z[0][1]=z[1][1]=z[1][0]=1;
	sol[0][0]=sol[1][1]=1;
	mat_pow(n-1);
	ofstream out("kfib.out");
	out<<sol[1][1];
	out.close();
}