#include <bits/stdc++.h>
#define MOD 666013
#define ll long long
using namespace std;

ll M[2][2]={{0,1},{1,1}},B[2][2]={{0,1},{1,1}};
int n;

void p(){
	ll S[2][2]={{0,0},{0,0}};
	for(int i=0;i<2;i++){
		for(int k=0;k<2;k++){
			for(int j=0;j<2;j++){
				S[i][k]+=M[i][j]*M[j][k];
				S[i][k]%=MOD;
			}
		}
	}
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			M[i][j]=S[i][j];
		}
	}	
}

void fp(int k){
	if(k<=1)return;
	fp(k/2);
	p();
	if(k%2){
		ll S[2][2]={{0,0},{0,0}};
		for(int i=0;i<2;i++){
			for(int k=0;k<2;k++){
				for(int j=0;j<2;j++){
					S[i][k]+=M[i][j]*B[j][k];
					S[i][k]%=MOD;
				}
			}
		}
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				M[i][j]=S[i][j];
			}
		}	
	}
}

int main(){
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");
	int f0=0,f1=1;
	cin>>n;
	if(n==0)cout<<f0;
	else if(n==1)cout<<f1;
	else if(n==2)cout<<1;
	else{
		fp(n-2);
		ll s=0;
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				if(!j){
					s+=M[i][j]*f0;
				}else{
					s+=M[i][j]*f1;
				}
				s%=MOD;
			}
		}
		cout<<s;
	} 
	return 0;
}