#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],b[2][2];
void inmultire(int a[][2], int b[][2])
{
	int aux[2][2];
	
	aux[0][0]=(1ll*a[0][0]*b[0][0]%MAX + 1ll*a[0][1]*b[1][0]*MAX)%MAX;
	aux[0][1]=(1ll*a[0][0]*b[0][1]%MAX + 1ll*a[0][1]*b[1][1]%MAX)%MAX;
	aux[1][0]=(1ll*a[1][0]*b[0][0]%MAX + 1ll*a[1][1]*b[1][0]%MAX)%MAX;
	aux[1][1]=(1ll*a[1][0]*b[0][1]%MAX + 1ll*a[1][1]*b[1][1]%MAX)%MAX;
	
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			a[i][j]=aux[i][j];
}

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

int main()
{
	int k;
	f>>k;
	
	b[0][1]=b[1][0]=b[1][1]=1;
	a[0][0]=a[1][1]=1;
	
	putere(a,k);
	
	g<<a[1][1];
	f.close();
	g.close();
	return 0;
	
}