#include<cstdio>
#include<cstring>
#include<fstream>
using namespace std;
int z[2][2],sol[2][2],tmp[2][2],n;
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]+=(1LL*a[i][k]*b[k][j])%666013;
}
inline void mat_pow(int p) {
	int i;
	for (i=0;(1<<i)<=p;i++) {
		if(p&(1<<i)) {
			memset(tmp,0,sizeof(tmp));
			inmultire(sol,z);
			memcpy(sol,tmp,sizeof(tmp));
			}
		memset(tmp,0,sizeof(tmp));
		inmultire(z,z);
		memcpy(z,tmp,sizeof(tmp));
		}
}
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();
}