#include <fstream>
#include <cstdio>
#include <cstring>
#define MOD 666013
using namespace std;

int n,A[2][2],B[2][2],C[2][2];

void inm(int A[][2],int B[][2]) {
	
	int i,j,k;
	
	memset(C,0,sizeof(C));
	
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			for(k=0;k<2;k++)
				C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
	
}	
int lgput() {
	
	int mask=1;
	
	while(mask<=n) {
		
		if(mask&n) {
			inm(A,B);
			memcpy(B,C,sizeof(B));
			}
		
		inm(A,A);
		memcpy(A,C,sizeof(A));
		
		mask<<=1;
		}
	
	return B[1][1];
	
}
int main() {
	
	ifstream in("kfib.in");
	ofstream out("kfib.out");
	in>>n;
	
	// init B matricea unitate
	B[0][0]=B[1][1]=1;
	// init A matricea sol^1
	A[0][1]=A[1][0]=A[1][1]=1;
	
	--n;
	out<<lgput()<<'\n';;
	
	in.close();
	out.close();
	
	return 0;
	
}