/*
 * =====================================================================================
 *
 *       Filename:  fibonacci.c
 *
 *    Description:  Al n-ulea termen din sirul Fibonacci in timp
 *    				logaritmic
 *
 *        Version:  1.0
 *        Created:  12/08/2010 10:15:42 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Dodon Victor (), 
 *        Company:  Calculatoare ,UPB
 *
 * =====================================================================================
 */

#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>
#define ok 666013

void mult_matrice(int a[][2],int b[][2],int c[][2])
{
	int i,j,k;
	for (i=0;i<2;++i)
		for (j=0;j<2;++j){
			c[i][j]=0;
			for (k=0;k<2;++k)
				c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j]) % ok;
		}
}

void set ( int mat[][2],int k )
{
    mat[0][0]=mat[0][1]=mat[1][0]=mat[1][1]=k;
}

void copy( int dest[][2],int src[][2])
{
	int i,j;
	for (i=0;i<2;i++)
		for (j=0;j<2;j++)
			dest[i][j]=src[i][j];
}

void fibonacci(int n,int f[][2],int sol[][2])
{
	int aux[2][2];
	set(sol,0);
	sol[0][0]=sol[1][1]=1;

	while (n){
		if (n&1){
			set(aux,0);
            mult_matrice(sol,f,aux);
			copy(sol,aux);
		}
		set(aux,0);
		mult_matrice(f,f,aux);
		copy(f,aux);
		n>>=1;
	}

}

int main ()
{
	int f[2][2],sol[2][2];
	int i,j,n;

	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);

	scanf("%d",&n);
	for (i=0;i<2;++i)
		for (j=0;j<2;++j)
			f[i][j]=i||j;

	fibonacci(n-1,f,sol);
    printf("%d\n",sol[1][1]);
	return EXIT_SUCCESS;
}