#include<fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long aux[3][3],m[3][3],rez[3][3],n;
void copy(long long A[3][3]){
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			A[i][j]=aux[i][j];
}
void multi(long long A[3][3],int la,int ca,long long B[3][3],int lb,int cb){
	for(int i=1;i<=la;i++)
		for(int j=1;j<=cb;j++){
			aux[i][j]=0;
			for(int k=1;k<=ca;k++){
				aux[i][j]=aux[i][j] +(A[i][k]*B[k][j])%mod;
				
			}
			aux[i][j]%=mod;
		}
	copy(A);
}
void lgput(long long A[3][3],long long P[3][3],long long put){
	while(put){
		if(put%2==1){
			multi(P,2,2,A,2,2);
		}
		multi(A,2,2,A,2,2);
		put>>=1;
	}
}
int main (){
	f>>n;
	m[1][1]=m[2][2]=1;
	rez[2][1]=rez[1][2]=rez[2][2]=1;
	lgput(rez,m,n-1);
	g<<m[2][2]%mod;
	return 0;
}