#include<fstream>
#define MOD 666013

using namespace std;

unsigned long long A[3][3],k,a,b,c;
unsigned long long R[3][3];

int main(){
	
	ifstream f("kfib.in");
	ofstream g("kfib.out");

	f>>k;
	
	
	A[1][1]=A[2][1]=A[1][2]=1;
	A[2][2]=0;
	R[1][1]=R[2][1]=R[1][2]=1;
	R[2][2]=0;
	//k--;
	
	while( k ){
		
		if( k&1 ) {
			
			a = R[1][1];
			R[1][1] = (R[1][1]*A[1][1] + R[1][2]*A[2][1])%MOD;
			R[1][2] = (a*A[1][2] + R[1][2]*A[2][2])%MOD;
			a=R[2][1];
			R[2][1] = (R[2][1]*A[1][1] + R[2][2]*A[2][1])%MOD;
			R[2][2] = (a*A[1][2] + R[2][2]*A[2][2])%MOD;
			
		}
		
		a = A[1][1];
		A[1][1] = (A[1][1]*A[1][1] + A[1][2]*A[2][1])%MOD;
		b=A[2][1];c=A[1][2];
		A[1][2] = (a*A[1][2] + A[1][2]*A[2][2])%MOD;
		A[2][1] =( a*A[2][1] + A[2][2]*A[2][1])%MOD;
		A[2][2] = (A[2][2]*A[2][2] + b*c)%MOD;
		
		k>>=1;
	}
			
	g<<(R[2][2])%MOD;
	return 0;
}