#include <fstream>
#include <string.h>

#define rest 666013

using namespace std;

long long K;
int N=2;


void inm(long long A[3][3],long long B[3][3])
{
	long long AUX[3][3];
	memset(AUX,0,sizeof(AUX));
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
		{
			for(int z=1;z<=N;z++)
				AUX[i][j]=(AUX[i][j]+A[i][z]*B[z][j]%rest)%rest;
		}
	memcpy(A,AUX,sizeof(AUX));
}


inline void citire()
{
	fstream fin("kfib.in",ios::in);
	
	fin>>K;
	
	fin.close();
}

inline void afisare(long long A[3][3])
{
	fstream fout("kfib.out",ios::out);
	
	fout<<A[2][1]<<"\n";
	
	fout.close();
}

int main(int argc, char* argv[])
{
	citire();
	
	long long A[3][3];
	long long B[3][3];
	A[1][1]=1; A[1][2]=0; A[2][1]=0; A[2][2]=1;
	B[1][1]=0;B[1][2]=1; B[2][1]=1; B[2][2]=1;
		
	for(int i=0;((1<<i)<=K);i++)
	{
		if(K & (1<<i))
		{
			inm(A,B);
		}
		inm(B,B);
	}
	
	afisare(A);
}