#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>
using namespace std;

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

const long long mod=666013;

struct mat{
	long long m[2][2];
	mat(){
		for(int i=0;i<2;i++){
			for(int k=0;k<2;k++)
				m[i][k]=0;
		}
	}

	mat operator*(const mat&other){
		mat result;

		for(int line=0;line<2;line++){
			for(int column=0;column<2;column++){
				long long sum=0;
				for(int i=0;i<2;i++){
					sum=(sum+(m[line][i]*other.m[i][column])%mod)%mod;
				}

				result.m[line][column]=sum;
			}	
		}
		return result;
	}
};

mat fpow(const mat&base,int power){
	mat fact=base;	
	mat result;
	result.m[0][0]=result.m[1][0]=result.m[0][1]=result.m[1][1]=1;

	for(int i=1;i<=power;i=i<<1){
		if((power&i)!=0){
			result=result*fact;	
		}
		fact=fact*fact;
	}
	return result;
}

int main(){
	mat q,base;
	base.m[0][0]=1;
	base.m[0][1]=1;
	base.m[1][0]=1;

	q.m[0][1]=0;
	q.m[0][0]=1;

	int power;
	in>>power;
	if(power==0){
		out<<0;
	}
	else{
		power--;
		mat result=q*fpow(base,power);
		out<<result.m[0][1];
	}
	return 0;
}