#include <stdio.h>

FILE *f,*s;

int n;

long long int m1[5][5],m2[5][5];

void Transforma(long long int m2[5][5], long long int m1[5][5])
{
    long long int x1=m2[1][1],y1=m2[1][2],z1=m2[2][1],t1=m2[2][2],x2=m1[1][1],y2=m1[1][2],z2=m2[2][1],t2=m1[2][2];
	
    m2[1][1]=(x1*x2+y1*z2)%666013;
    m2[1][2]=(x1*y2+y1*t2)%666013;
    m2[2][1]=(z1*x2+t1*z2)%666013;
    m2[2][2]=(z1*y2+t1*t2)%666013;
 
}

long long int kFib(long long int p)
{
    while(p)
    {
        if(p%2)
            Transforma(m2, m1);
		
        Transforma(m1,m1);
		
        p/=2;
    }
	
    return m2[2][1]%666013;
}

int main()
{
	f=fopen("kfib.in","r");
	s=fopen("kfib.out","w");
	
	fscanf(f,"%d",&n);
	
	m1[1][1]=0;
	m1[1][2]=m1[2][1]=m1[2][2]=1;
	
	m2[1][1]=m2[2][2]=1;
	m2[1][2]=m2[2][1]=0;
	
	fprintf(s,"%d",kFib(n));
	
	fclose(s);
	
	return 0;
}