#include <stdio.h>
 
FILE *f,*s;
 
long long int n;
 
long long int m1[2][2]={{0,1},{1,1}},m2[2][2]={{1,0},{0,1}}; 
 
void Transforma(long long int m2[2][2], long long int m1[2][2])
{
    long long int x1=m2[0][0],y1=m2[0][1],z1=m2[1][0],t1=m2[1][1],x2=m1[0][0],y2=m1[0][1],z2=m1[1][0],t2=m1[1][1];
     
    m2[0][0]=(x1*x2+y1*z2)%666013;
    m2[0][1]=(x1*y2+y1*t2)%666013;
    m2[1][0]=(z1*x2+t1*z2)%666013;
    m2[0][1]=(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[1][0]%666013;
}
 
int main()
{
    f=fopen("kfib.in","r");
    s=fopen("kfib.out","w");
     
    fscanf(f,"%lld",&n);
	
    fprintf(s,"%lld",kFib(n));
     
    fclose(s);
     
    return 0;
}