#include <fstream>
#include <iostream>
using namespace std;

#define MOD 666013

fstream fin("kfib.in",ios::in);
fstream fout("kfib.out",ios::out);

struct mat{
	long long x[3][3];
	mat operator*(mat& m){
		mat tmp;
		for(int i=1;i<=2;i++){
			for(int j=1;j<=2;j++){
				tmp.x[i][j]=0;
				for(int k=1;k<=2;k++){
					tmp.x[i][j]=(tmp.x[i][j]+1l*x[i][k]*m.x[k][j]%MOD)%MOD;
				}
			}
		}
		return tmp;
	}
};

int main(){
	int n;
	
	fin>>n;
	
	n--;
	
	mat a,q;
	a.x[1][1]=0,a.x[1][2]=1,a.x[2][1]=1,a.x[2][2]=1;	
	q.x[1][1]=q.x[2][2]=1;
	q.x[1][2]=q.x[2][1]=0;
		
	while(n){
		if(n&1){
			q=q*a;
		}
		a=a*a;
		n>>=1;
	}
	
	fout<<q.x[2][2]<<endl;
		
	fin.close();
	fout.close();
	return 0;
}