# include <fstream>
#define MOD 666013

using namespace std;
typedef int MATRICE[2][2];
MATRICE a={{0,1},{1,1}};

void produs(MATRICE a, MATRICE b, MATRICE rez){
	rez[0][0]=((long long)a[0][0]*b[0][0]+(long long)a[0][1]*b[1][0])%MOD;
	rez[0][1]=((long long)a[0][0]*b[0][1]+(long long)a[0][1]*b[1][1])%MOD;
	rez[1][0]=((long long)a[1][0]*b[0][0]+(long long)a[1][1]*b[1][0])%MOD;
	rez[1][1]=((long long)a[1][0]*b[0][1]+(long long)a[1][1]*b[1][1])%MOD;
}

void putere(int n, MATRICE rez){
	if(n==1)
		for(int i=0;i<2;i++) for (int j=0;j<2;++j) rez[i][j]=a[i][j];
	else
		if(n%2==0){
			MATRICE  x;
			putere(n/2,x);
			produs(x,x,rez);
		}
		else{
			MATRICE x;
			putere(n-1,x);
			produs(x,a,rez);
		}
}

int main(){
	int n;
	ifstream fin("kfib.in");
	fin>>n;
	MATRICE b;
	if(n==0)
		b[1][1]=0;
	else
		putere(n-1,b);
	ofstream fout("kfib.out");
	fout<<b[1][1]<<endl;
	return 0;
}