#include<stdlib.h>
#include<fstream>
#include<stdio.h>
#define MAX 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int a[2][2],b1[2][2];
void inmultire(int a[][2], int b[][2])
{
	int aux[2][2]={{0,0},{0,0}}; 
	
	aux[0][0]=( a[0][0]*b[0][0]%MAX + a[0][1]*b[1][0]%MAX)%MAX;
	
	//g<<"part:"<<aux[0][0]<<"\n";
	
	aux[0][1]=( a[0][0]*b[0][1]%MAX + a[0][1]*b[1][1]%MAX)%MAX;
	
	//g<<"part:"<<aux[0][1]<<"\n";
	
	aux[1][0]=( a[1][0]*b[0][0]%MAX + a[1][1]*b[1][0]%MAX)%MAX;
	
	//g<<"part:"<<aux[1][0]<<"\n";
	
	aux[1][1]=( a[1][0]*b[0][1]%MAX + a[1][1]*b[1][1]%MAX)%MAX;
	
	//g<<"part:"<<aux[1][1]<<"\n";
	
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			a[i][j]=aux[i][j];
	/*
	g<<"matrice:";
	for(int i=0;i<2;i++)
	{
			g<<"\n";
			for(int j=0;j<2;j++)
			{
					g<<" "<<a[i][j];
			}
	}
	g<<"\n";*/
}

void putere(int a[][2], int p)
{
	while(p)
	{
		if(p%2==1) 
			{
				inmultire(a,b1);
				p--;
			}
		else 
			{
				inmultire(a,a);
				p=p/2;
			}
	}
}

int main()
{
	int k = 0;
	f>>k;
	//g<<k<<"\n";
	 a[0][0]=b1[0][0]=0;
     a[0][1]=b1[0][1]=1;
     a[1][0]=b1[1][0]=1;
     a[1][1]=b1[1][1]=1;
	
	if(k==0) g<<"0";
	if(k==1||k==2) g<<"1";
	if(k==3) g<<"2";
	if(k>3){
				putere(a,k-2);
				g<<a[1][1];
			}
			
	f.close();
	g.close();
	return 0;
	
}