#include <fstream>
using namespace std;

#define NUMBER 666013

typedef long long mat22[2][2];

mat22 TMP;
mat22 R = {{1,0},{0,1}};
mat22 C = {{0,1},{1,1}};

void multiply(mat22 A, mat22 B)
{
	TMP[0][0] = (A[0][0]*B[0][0]+A[0][1]*B[1][0]) % NUMBER;
	TMP[0][1] = (A[0][0]*B[0][1]+A[0][1]*B[1][1]) % NUMBER;
	TMP[1][0] = (A[1][0]*B[0][0]+A[1][1]*B[1][0]) % NUMBER;
	TMP[1][1] = (A[1][0]*B[0][1]+A[1][1]*B[1][1]) % NUMBER;
}

int main(void)
{
	int k;	

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

	f >> k;
	
	if (k>1)
	{
		k-=2;		
		while (k>0)
		{
			if (k&1) 
			{				
				multiply(R,C);
				memcpy(&R,&TMP,sizeof(mat22));
				k ^= 1;
			}
			else
			{
				multiply(C,C);
				memcpy(&C,&TMP,sizeof(mat22));
				k >>= 1;
			}
		}

		g << (R[0][1]+R[1][1]) % NUMBER <<"\n";
	}
	else g << k << "\n";

	f.close();
	g.close();

	return 0;
}