#include<fstream>
#include<cstring>
#define MOD 666013
using namespace std;
int K;
long long A[2][2]={{0,1},{1,1}};
long long B[2][2]={{0,1},{1,1}};
long long rez[2][2]={{0,0},{0,0}};

void InmultesteMatrici(long long rez[2][2],long long A[2][2],long long B[2][2])
{
	rez[0][0]=((A[0][0]*B[0][0])%MOD + (A[0][1]*B[1][0])%MOD)%MOD;
	rez[0][1]=((A[0][0]*B[0][1])%MOD + (A[0][1]*B[1][1])%MOD)%MOD;
	rez[1][0]=((A[1][0]*B[0][0])%MOD + (A[1][1]*B[1][0])%MOD)%MOD;
	rez[1][1]=((A[1][0]*B[0][1])%MOD + (A[1][1]*B[1][1])%MOD)%MOD;
}

void LgPut(int k)
{
	int i=1,j=k;
	while(j>1)
	{
		i=i*2;
		j=j/2;
	}
	i=i/2;
	while(i)
	{
		InmultesteMatrici(rez,A,A);
		memcpy(A,rez,4*sizeof(long long));
		if(k&i)
		{
			InmultesteMatrici(rez,B,A);
			memcpy(A,rez,4*sizeof(long long));
		}
		i=i/2;
	}
}

int main()
{
	ifstream fin("kfib.in");
	fin>>K;
	fin.close();
	
	LgPut(K-1);
	
	ofstream fout("kfib.out");
	fout<<A[1][1]<<"\n";
	fout.close();
	return 0;
}