/*
 * =====================================================================================
 *
 *       Filename:  fibonacci.c
 *
 *    Description:  Calcularea a n-ului 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(long long a[][2],long long b[][2],long long 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]+=(a[i][k]*b[k][j]) % ok;
		}
}

void print ( long long mat[][2] )
{
	printf("%lld %lld\n%lld %lld\n",mat[0][0],mat[0][1],mat[1][0],mat[1][1]);
}

void fibonacci(int n,long long f[][2])
{
	long long x[2][2],aux[2][2],rez[2][2];

	memcpy(x,f,sizeof(x));
	memset(f,0,sizeof(f));
	f[0][0]=f[1][1]=1;

	while (n){
		if (n&1){
            memset(aux,0,sizeof(aux));
			mult_matrice(f,x,aux);
			memcpy(f,aux,sizeof(rez));
			print(f);
			printf("--\n");
		}
		memset(aux,0,sizeof(aux));
		mult_matrice(x,x,aux);
		memcpy(x,aux,sizeof(x));
		n>>=1;

	}
	memcpy(f,rez,sizeof(f));

}

int main ()
{
	long long f[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,f);
    printf("%lld\n",f[1][1]);
	return EXIT_SUCCESS;
}