#include <fstream>
#include <cstring>

using namespace std;

#define MOD 666013

class matrix{
	public:
		long long a[3][3];
		matrix(){
			memset(a,0,sizeof a);
		}
		void init(){
			a[1][2]=a[2][1]=a[2][2]=1;
		}
		
		void operator*=(matrix m){
			matrix r;
			for(int i=1;i<=2;i++){
				for(int j=1;j<=2;j++){
					for(int k=1;k<=2;k++)
						r.a[i][j]+=a[i][k]*m.a[k][j];
					r.a[i][j]%=MOD;
				}
			}
			*this=r;
		} 
};


matrix lgput(matrix m,int p){

	matrix sol;
	sol.a[1][1]=sol.a[2][2]=1;
	while(p){
		if(p&1)
			sol*=m;
		m*=m;
		p>>=1;		
	}
	return sol;
}

int main(){

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

	int k;

	f >> k;
	if(k==0) g <<"0";
	else{ 
		matrix z,c;
		z.init();
		z=lgput(z,k-1);
		c.a[1][1]=0;
		c.a[1][2]=1;	
		c*=z;
		g << c.a[1][2];
	}
}